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

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

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

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

 

Задача

 

Даны целое число 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 56 8 12 15 17 18 20 25;

 

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

 

m = ;

3 5 68 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.