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

Последовательный поиск

Постановка задачи: пусть дан массив из N элементов. Необходимо определить номер элемента, который обладает определенными свойствами (чаще всего речь идет просто об элементе с определенным значением, равным k), или установить что такого элемента в массиве нет.

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

Пример фрагмента программы

const

N = 100;

var

a: array[1..N] of integer;

i, k: integer;

begin

{ввод массива, k}

i: =1;

while (i< =N)and(a[i]< > k) do inc(i);

{после окончания цикла i равно номеру искомого элемента, а если элемент не найден, то i=N+1 }

end.

Использование цикла while вместо for обусловлено сокращением количества сравнений, если нужный элемент находится близко к началу массива. В этом случае, как только элемент будет найден, цикл прекратит свою работу.

Возможна следующая оптимизация этого алгоритма. Добавим искомый элемент на N+1 место в массиве и перепишем программу следующим образом:

const

N = 100;

var

a: array[1..N+1] of integer;

i, k: integer;

begin

{ввод массива, k}

a[N+1]: =k;

i: =1;

while (a[i]< > k) do inc(i);

{после окончания цикла i равно номеру искомого элемента}

end.

Очевидно, что при такой модификации элемент будет найден либо в середине массива, либо на в позиции N+1, поэтому проверку на выход за границы массива можно не делать, потому что условие цикла (a[i]< > k) обязательно нарушится еще в границах массива. После отработки этого цикла i равно N+1, если элемента с заданным значением в массиве не найдено, или равно номеру этого элемента.

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

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

Рассмотрим пример. Пусть дан массив из 9 элементов, упорядоченный по возрастанию их значений.

Пусть требуется найти номер элемента, значение которого равно -3. Сравним это значение с первым элементом массива (-3)< 2. Из условия того, что массив упорядочен по возрастанию следует, что элементы с б о льшими номерами будут обладать б о льшими значениями, то есть остальные числа в массиве гарантировано больше чем 2. Отсюда можно сделать вывод, что числа (-3) в массиве нет.

Пусть требуется найти элемент со значением 44. Сравним данное число с первым элементом. 44> 2. Следовательно, можно предположить, что в массиве число 44 встречается. Теперь сравним это число с последним элементом массива (из условия упорядоченности массива, его последний элемент является наибольшим, а все остальные элементы заведомо меньше его). 44> 36. Следовательно, в массиве числа 44 быть не может.

Пусть требуется найти элемент со значением 22. Сравним это число с крайними элементами массива, и убедимся, что такое число может присутствовать среди его элементов.

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

Элемент, стоящий в середине массива не тот, который нам нужен. (9< > 22). Тем не менее, этот элемент делит массив на две части: одну в которой искомого числа точно быть не может (в данном примере это левая половина массива; из условия упорядоченности все элементы, стоящие слева от 9 будут меньше этого числа) и вторую, в которой можно продолжать поиск.

Рассмотрим теперь правую часть массива. Найдем элемент, стоящий в ее середине.

Это значение равно искомому, процесс поиска окончен.

Пусть требуется найти элемент со значением 7. Сравним это число с крайними элементами массива и убедимся что поиск имеет смысл.

Рассмотрим элемент, находящийся в середине массива.

Этот элемент не равен искомому, следовательно, поиск необходимо продолжить. Так как 9> 7, следовательно, правую половину массива можно исключить из рассмотрения, и продолжить поиск только в левой. Рассмотрим элемент, стоящий в середине левой половины:

Этот элемент снова не равен 7, следовательно поиск надо продолжить. Из условия упорядоченности массива, поиск будем продолжать в правой части нашего «укороченного» массива.

Рассмотрим элемент, находящийся в середине выделенной части массива.

Этот элемент не равен искомому. Однако, в результате постоянного уменьшения область поиска в массиве уменьшилась до трех элементов, и каждый из них был рассмотрен на каком-то шаге. Следовательно, процесс поиска окончен, результат — сообщение о том, что элемент с таким значением в массиве отсутствует.

На этих примерах видно, что с каждым шагом размер области поиска в массиве уменьшается в два раза, что приводит к сокращению числа операций. Например, за 10 шагов размер области поиска будет уменьшен в 1024 раза, а для массива из 1000 000 элементов понадобится всего 20 шагов.

Количество операций в данном методе равно O(log n).

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

const

N = 100;

var

a: array [1..N] of integer;

i: integer;

k: integer;

c, left, right: integer;

begin

{ввод данных}

left: =1;

right: =N;

if a[1]=k then write('Ответ=', 1)

else

if a[N]=k then write('Ответ=', N) {сразу проверим, не является ли искомый}

else {элемент крайним}

if k< a[left] then write('Нет числа') {сравним с крайними, решим вопрос: }

else {а стоит ли вообще искать? }

if k> a[right] then write('Нет числа')

else

begin

repeat {цикл поиска: найдем номер в середине}

c: =(left+right) div 2; {текущей области поиска}

if a[c]< k then left: =c;

if a[c]> k then right: =c;

until (a[c]=k)or(right-left< =1); {пока элемент не найден, или пока область}

{поиска не стала состоять всего из двух соседних}

{элементов}

if a[c]=k then write('Ответ=', c)

else write('Нет числа');

end;

end.

Здесь left и rght — это номера элементов массива, которые являются границами текущей области поиска. Например, если left=3 и right=7 это значит что поиск ведется среди элементов с номерами от 3 до 7 и именно в этой области на данном шаге будет искаться середина.

Существует рекурсивная реализация данного метода, которая является более короткой и красивой, и мы вернемся к ней в теме «Рекурсия».