2.1.2. Поиск с барьером

Единственно возможное убыстрение алгоритма линейного поиска заключается в упрощении логического условия. Для этого следует увеличить количество элементов массива A на один элемент со значением ключа поиска , то есть . Этот дополнительный элемент называется «барьером». Его введение позволяет алгоритм линейного поиска представить в виде:

пока выполнить

всё-пока

Введение барьера позволяет не проверять каждый раз в цикле условие, связанное с границами массива.

Выход из цикла, в котором теперь остается только условие совпадения с ключом поиска, может произойти либо на найденном элементе, либо на барьере. Таким образом, после выхода из цикла проверяется, не барьер ли мы нашли? Вычислительная сложность поиска с барьером меньше, чем у линейного поиска, но также является величиной того же порядка, что и N - количество элементов массива.

Существует два способа установки барьера: дополнительным элементом или вместо крайнего элемента массива.

ПРИМЕР: Поиск с барьером

program Poisk_Bar1;

var A:array[1..101] of integer;

N,X,i:integer;

begin

read(N); {N<=100}

for i:=1 to N do read(A[i]);

read(X);

A[N+1]:=X; {установка барьера дополнительным элементом}

i:=1; {i:=0;}

while A[i]<>X do i:=i+1;

{repeat i:=i+1; until A[i]=X;}

if i<=N then write('первое вхождение числа ',X,' в массив A на ',i,' месте')

else write('не нашли');

end.

program Poisk_Bar2;

var A:array[1..100] of integer;

N,X,i,y:integer;

begin

read(N); {N<=100}

for i:=1 to N do read(A[i]);

read(X);

y:=A[N]; {сохранение последнего элемента}

A[N]:=X; {установка барьера на последнее место массива}

i:=1; {i:=0;}

while A[i]<>X do i:=i+1;

{repeat i:=i+1; until A[i]=X;}

if (i<N) or (y=X) then

write('первое вхождение числа ',X,' в массив A на ',i,' месте')

else write('не нашли');

A[N]:=y; {восстановление последнего элемента массива}

end.

2.1.3. Двоичный (бинарный) поиск

Алгоритм двоичного поиска можно использовать для поиска элемента только в упорядоченном массиве . Упорядоченность массива позволяет при поиске использовать условия в виде неравенств.

Принцип двоичного поиска:

• Исходный массив делится пополам и для сравнения выбирается средний элемент. Если он совпадает с искомым, то поиск заканчивается.

• Если средний элемент меньше искомого, то все элементы левее его также будут меньше искомого. Следовательно, их можно исключить из процесса дальнейшего поиска, оставив только правую часть массива. Аналогично, если средний элемент больше искомого, то отбрасывается правая часть, а остаётся левая.

• На втором этапе выполняются аналогичные действия над оставшейся половиной массива. В результате после второго этапа останется ¼ массива.

• Процесс продолжается до тех пор, пока или элемент будет найден, или длина зоны поиска станет равной нулю. В последнем случае поиск будет безуспешен.

Алгоритм двоичного поиска имеет вид:

пока выполнить

если то

иначе

всё-если

всё-пока

Существуют две модификации этого алгоритма для поиска первого и последнего вхождения. Все зависит от того, как выбирается средний элемент: округлением в меньшую или большую сторону. Например, округление c:=(L+R+1) div 2 даёт середину с округлением в большую сторону. В случае округления в меньшую сторону средний элемент относится к левой части массива, а при округлении в большую сторону – к правой.

В процессе работы алгоритма двоичного поиска размер фрагмента, где этот поиск должен продолжаться, каждый раз уменьшается примерно в два раза. Это обеспечивает вычислительную сложность алгоритма порядка , где N - количество элементов массива.

ПРИМЕР: Поиск в упорядоченном по возрастанию массиве первого вхождения числа X.

program Poisk3a;

var A:array[1..100] of integer;

N,X,L,R:integer;

begin

read(N); {N<=100}

write('введите упорядоченный по возрастанию массив');

for i:=1 to N do read(A[i]);

read(X);

L:=1; R:=N; {левая и правая граница фрагмента для поиска}

while L<R do

begin

c:=(L + R) div 2; {середина с округлением в меньшую сторону}

if X>A[c] then

{если массив упорядочен по убыванию, то if X<A[c]}

L:=c+1 {выбор правой половины без середины с помощью изменения L}

else R:=c;

{выбор левой половины с серединой с помощью изменения R}

end;

if X=A[L] then {здесь L = R, но не всегда = c}

write('первое вхождение числа ' , X, ' в массив A на позиции ', L)

else write('не нашли');

end.

2.1.4. ЗАДАНИЕ

1. Сравнить время выполнения линейного поиска в массиве случайных чисел при = 100, 500, 1000, 3000, 10000. В каждом случае использовать не менее трёх массивов одного размера с заданным числом элементов. Построить диаграмму зависимости времени поиска и числа сравнений от числа элементов в массиве.

2. Провести сравнение времени поиска и количества повторений цикла при линейном и двоичном поиске в предварительно отсортированном массиве.

3. Исследовать эффективность введения «барьера» при линейном поиске. Представить таблицы, иллюстрирующие сделанные выводы.

4. В отчёте привести тексты программ с необходимыми комментариями, позволяющими пояснить суть выполняемых действий.

ЛИТЕРАТУРА

1. Кнут Д. Искусство программирования для ЭВМ в 3 т.- М.: Мир, 1978.- Т.3. Сортировка и поиск.

2. Вирт Н. Алгоритмы и структуры данных. – С.-Пб.: Невский диалект.