Бинарный поиск
Как было отмечено выше, если никаких дополнительных сведений о массиве, в котором хранятся данные, нет то ускорить поиск нельзя. Если же заранее известна некоторая информация о данный, среди которых ведется поиск, например,
массив данных отсортирован, удается существенно сократить время работы, применяя другие методы поиска.
Одним из методов поиска, более эффективным, чем линейный, является бинарный ( двоичный ) поиск, называемый также методом половинного деления. При его использовании на каждом шаге область поиска сокращается вдвое. Рассмотрим применение этого метода для решения конкретной задачи.
Задача
Даны целое число 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.