Бинарный поиск

Линейный поиск с использованием барьера

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

Постараемся оставить в заголовке цикла лишь простое условие а [ i ]<>x. Для этого используем следующий прием. В массив на (n + 1) - e место запишем ископаемый элемент x, который назовем барьерным. Тогда если в процессе работы программы обнаружится такой индекс i, что а [ i ] = x, то элемент будет найден, а если условие a[i] = x выполнится только при i = n + 1, то, значит, интересующего нас элемента в массиве нет. Таким образом, эта часть программы будет выглядеть так:

a [ n + 1 ]: = x; i: = 1;

While a [ i ]<>x Do Inc (i);

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

Программа линейного поиска с использованием барьера:

program n7;

const n=5;

var a:array[1..n+1] of integer;

{ массив из n элементов целого типа }

x:integer; { искомый элемент целого типа }

i,k:integer;

begin

writeln('Введите исходный массив:');

for i:=1 to n+1 do read(a[i]);

writeln('Введите x');

readln(x);

a[n+1]:=x; i:=1;

while (a[i]<>x) do begin

inc(i);

if a[i]=x then k:=i;

end;

writeln('a[',k,']=',x,'=x');

end.

Как было отмечено выше, если никаких дополнительных сведений о массиве, в котором хранятся данные, нет то ускорить поиск нельзя. Если же заранее известна некоторая информация о данный, среди которых ведется поиск, например,

массив данных отсортирован, удается существенно сократить время работы, применяя другие методы поиска.

Одним из методов поиска, более эффективным, чем линейный, является бинарный (двоичный) поиск, называемый также методом половинного деления. При его использовании на каждом шаге область поиска сокращается вдвое. Рассмотрим применение этого метода для решения конкретной задачи.

Задача

Даны целое число x и массив a[1..n], отсортированный в порядке убывания, то есть для любого k: 1 ≤ k < n: a[k-1] ≤ a[k]. Найти такое i, что a[i] = x, или сообщить, что элемента x в массиве нет.

Идея бинарного метода состоит в том, чтобы проверить, является ли x средним элементом массива. Если да, то ответ получен. Если нет, то возможны два случая:

· x меньше среднего элемента, следовательно, в силу упорядоченности массива a, можно исключить из рассмотрения все элементы массива, расположенные в нем правее среднего (так как они больше среднего элемента, который, в свою очередь, больше x), и применить этот метод к левой половине массива.

· x больше среднего элемента, следовательно, рассуждая аналогично, можно исключить из рассмотрения левую половину массива и применить этот метод к его правой части.

Средний элемент и в том, и в другом случае в дальнейшем не рассматривается. Таким образом, на каждом шаге отсекается та часть массива, где заведомо не может быть обнаружен элемент x.

Рассмотрим пример

Пусть x = 6, а массив а состоит из 10 элементов:

3 5 6 8 12 15 17 18 20 25.

1 -й шаг: найдем номер среднего элемента:

m = .Так как 6 < a [ 5 ], далее можем рассматривать только элементы, индексы которых меньше 5. Об остальных элементах можно сразу сказать, что они

больше x вследствие упорядоченности массива, и среди них искомого элемента нет:

3 5 6 8 12 15 17 18 20 25;

2- й шаг: рассматриваем лишь первые 4 элемента массива;

находим индекс среднего элемента этой части:

m =

6 > a [ 2 ], следовательно, первый и второй элементы из рассмотрения исключаем:

3 5 6 8 12 15 17 18 20 25;

3 -й шаг: рассматриваем 2 элемента; значение

m = ;

3 5 6 8 12 15 17 18 20 25;

а [ 3 ]= 6! Элемент найден, его номер - 3.

Примечание: Вообще говоря выбор значения m можно осуществлять случайным образом, корректность алгоритма от способа выбора m не зависит. Но на эффективность алгоритма выбор m влияет, так как мы хотим на каждом шаге исключить из дальнейшего рассмотрения как можно больше элементов. Оптимальным будет выбор среднего элемента, потому что при этом в любом случае будет исключаться половина массива.

В общем случае значение m = , где l - индекс первого, а r - индекс последнего элемента рассматриваемой части массива.

program n8;const n=10;var x,l,r,m,i:integer; f:boolean; a:array[1..n] of integer;begin writeln('Введите исходный массив:'); for i:=1 to n do read(a[i]); writeln('Введите x'); readln(x); l:=1; r:=n; f:=false;

while (l<=r)and not f do

begin

m:=(l+r) div 2;

if a[m]=x then f:=true else if a[m]<x then l:=m+1 else r:=m-1;

end;

writeln('a[',m,']=',x,'=x');

end.

Программа этой же сортировки с использованием барьера.

program n9;const n=10;var x,l,r,m,i:integer; f:boolean; a:array[1..n] of integer;

begin

writeln('Введите исходный массив:');

for i:=1 to n do read(a[i]);

writeln('Введите x');

readln(x);

l:=1;

r:=n;

f:=false;

while (l<=r)and not f do

begin

m:=(l+r) div 2;

if a[m]=x then f:=true else if a[m]<x then l:=m+1 else r:=m-1;

end;

writeln('a[',m,']=',x,'=x');

end.

Дата добавления: 2014-11-09