Если массив упорядочен по возрастанию или убыванию, то можно применить более быстрые методы поиска, такие как, например, бинарный (методом деления пополам).
Рассмотрим пример. Пусть дан массив из 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 и именно в этой области на данном шаге будет искаться середина.
Существует рекурсивная реализация данного метода, которая является более короткой и красивой, и мы вернемся к ней в теме «Рекурсия».
