Едва ли не самой внушительной демонстрацией эффективности применения компьютеров являются задачи, в которых осуществляется поиск информации в некотором списке. Ранее мы использовали метод линейного (последовательного) поиска, суть которого заключается в последовательном просмотре всего списка элементов массива и сравнении значения очередного элемента с заданным для поиска. Этот метод поиска вполне эффективен на неупорядоченных массивах данных, а на предварительно отсортированных массивах значительно эффективнее выполнять поиск другими методами. Например, метод линейного поиска практически бесполезен при поиске информации в массивах большого размера, так как занимает много времени.
Один из эффективных метод поиска в больших отсортированных массивах является бинарный поиск, или поиск методом деления пополам. В основе этого метода лежит идея целенаправленных последовательных догадок о предполагаемом местоположении искомого элемента. Такой метод можно проиллюстрировать на пример шуточного совета, как поймать в Африке льва: ″Для начала разделим Африку пополам. Ясно, что лев находится только в одной половине. Та половина, в которой находится лев, снова делится пополам и т.д. Площадь Африки приблизительно 30 млн. км2. Следовательно, после примерно 45 делений мы получим площадку, не превышающую 1 м2. Теперь на такой площадке льва поймать нетрудно″.
Аналогично выполняется бинарный поиск элемента в упорядоченном массиве. Вместо просмотра подряд всех элементов массива его пополам. Так как массив отсортирован, то, сравнивая искомый элемент со значением среднего элемента массива, мы в состоянии сделать вывод, может ли быть элемент с таким значением в массиве и в какой половине он находится, т.е. определить область дальнейшего поиска. Затем делится пополам та часть массива, в которой находится элемент, и так до тех пор, пока рассматриваемая часть массива получится состоящей из одного элемента.
Составим программу, которая выполняет бинарный поиск заданного элемента в отсортированном массиве целых чисел, элементы которого имеют значения:
20,20,19,19,19,18,17,17,12,12,11,10,9,9,5,5,3,3,2,1.
Введем в разделе описания констант размер массива Count=20 и опишем массив целых чисел:
M: array [1.. Count] of byte=20,20,19,19,19,18,17,17,12,12,11,10,9,9,5,5,3,3,2,1.).
В разделе описания переменных опишем следующие переменные:
N-для хранения значения искомого элемента;
I-для указания очередного элемента массива;
First-указание индекса элемента - левой границы рассматриваемой части
массива;
Last-указание индекса элемента - правой границы рассматриваемой части
массива;
Found-логическая переменная, в которой будет записываться результат
поиска;
A-переменная, значение которой будет равно числу перестановок элементов.
В начале программы запишем вывод исходного массива на экран, затем вывод запроса искомого элемента, после чего считывание его значения в переменную N.
Перед началом поиска обнулим счетчик повторений А, установим левую и правую границы рассматриваемой части массива, а переменной Found присвоим значение False-элементы пока не найден. Данный фрагмент программы запишется так:
A: =0;
First: =1;
Last: = Count;
Found: =False;
Повторяющуюся процедуру бинарного поиска запишем с помощью оператора повтора repeat. Первый шаг бинарного поиска - деление исходного массива на две части можно записать так:
I: = (First+ Last) div 2
Условие поиска запишем оператором
if M[I]=N then Fond: = True
Если условие M[I]=N выполняется, то искомый элемент найден, переменной Found присваивается значение True, и управление передается за пределы оператора if. Если это условие не выполняется, то оператором
if M[I]>N then First: =I+1 else Last: =I-1;
проверяется условие M[I]>N. Если оно выполняется, значит значение искомого элемента расположено в правой части массива, поэтому левую границу части массива переносим в позицию I+1 (First: =I+1), иначе элемент нужно искать в левой части массива, а, значит правую границу части массива переносим в позицию I-1 (Last: =I-1). Затем нужно записать увеличение счетчика повторений при поиске A: =А+1. оператор повтора завершим записью условия окончания (Found) or (first>Last). Если это условие выполнится, т.е. если найдется искомый элемент или будет просмотрен весь массив, цикл завершится. Этот фрагмент программы можно записать так:
repeat
I: = (First+ Last) div 2;
if M[I]=N then Fond: = True
else
begin
if M[I]>N then First: =I+1;
else Last: =I-1;
end;
A: =А+1;
until (Found) or (First>Last);
{Повторить поиск}
{Разделить на две части}
{Искать элемент в правой части}
{Искать элемент в левой части}
{Увеличить счетчик числа итераций}
{Завершить, если найдется искомый элемент или будет просмотрен весь массив}
В заключительной части программы запишем условие вывода результата поиска. Если значение переменной Fond= True, то выведем на экран сообщение о том, какую позицию в массиве занимает искомый элемент, иначе выведем сообщение о том, что такого элемента в массиве нет. После чего выведем сообщение о том, сколько просмотров массива выполнялось в процессе поиска.
В целом текст программы будет записан следующим образом:
program Find Bin;
const
Count=s 20;
M: array [1.. Count] of byte=20,20,19,19,19,18,17,17,12,12,11,10,9,9,5,5,3,3,2,1.).
var
N, I, First, Last Byte;
A: integer;
Fond: boolean;
Begin
Writeln (′Исходный массив :′);
for I:=1 to Count do Write(M[I]:3,′′);
Writeln;
Writeln;
Write(′Введите значение элемента массива для поиска>′);
Readln (N);
A: =0;
First: =1;
Last: = Count;
Found: =False; {Элемент не найден}
Repeat {Повторить поиск}
I: = (First+ Last) div 2;{Разделить на две части}
if M[I]=N then Fond: = True else
begin
if M[I]>N then First: =I+1{Искать элемент в правой части}
else Last: =I-1;{Искать элемент в левой части}
end;
A: =А+1; (Увеличить счетчик числа итераций)
until (Found) or (First>Last);(Завершить, если найдется искомый элемент или будет просмотрен весь массив}
if Found then Writeln(′Искомый элемент′,N,′в массиве занимает′ ,I,′-ю позицию′) else Writeln (′В массиве нет искомого элемента′,N);
Writeln (′Поиск выполнен за′, А, ′итераций′);
end.
Запустите интегрированную среду программирования. Введите текст программы Find_Bin и запишите файл на диск под соответствующим именем, а затем откомпилируйте его. После того как компиляция выполнится успешно, запустите программу на исполнение в пошаговом режиме и наблюдайте изменения текущих значений переменных First, Last, I, M[I], а также значение выражений M[I]>N и (Found) or (First>Last). Обратите внимание на то, что бинарный поиск в сортированных массивах выполняется за небольшое число итераций.