Нами будет написано два варианта поиска в отсортированном массиве Массив (он отсортирован по неубыванию значений полей Ключ). Оба варианта будут оформлены в виде функций, возвращающих номер найденного элемента (т.е. элемента, ключ которого равен искомому или больше его; нами будет использована переменная с таким именем – ИскомыйКлюч).
Но что делать, если требуемого элемента в массиве нет? если подходящих элементов несколько? На эти вопросы можно отвечать по-разному – получатся различные алгоритмы. Например, в разделе 3.1 будем искать первый по порядку элемент, имеющий ключ, значение которого больше или равно значению искомого, а в разделе 3.2 – первый по порядку элемент, имеющий ключ, больший искомого (возможны и другие варианты). И в обоих случаях написанные нами функции будут возвращать 0, если необходимого элемента в массиве нет (например, в разделе 3.2 – если ключи всех элементов массива меньше или равны искомому).
3.1 Линейный поиск
Алгоритм очень простой: перебираем все элементы, начиная с первого, и ищем первый подходящий.
function ЛинейныйПоиск (Граница,ИскомыйКлюч:word): word
var I: word;
begin
for I:=1 to Граница do
if Массив[I].Ключ>=ИскомыйКлюч
then begin ЛинейныйПоиск:=I; exit; end;
ЛинейныйПоиск:=0;
end;
Ещё раз отметим, что выходом (т.е. возвращаемым значением) написанной нами функции является наименьший из номеров элементов, для которых выполнено условие Ключ>=ИскомыйКлюч (или 0, если таких элементов не найдено). Аналогично пишутся и другие, похожие варианты линейного поиска: найти в точности «равный» элемент, найти первый «больший» элемент и т.п.
3.2 Дихотомия (поиск делением пополам)
Рассмотрим такую игру: один игрок загадывает натуральное число (например, от 1 до 1024), а второй пытается его угадать с помощью минимального количества вопросов. При этом вопросы могут быть любыми, но есть ограничение: отвечать можно только «да» или «нет».
Алгоритм из предыдущего подраздела аналогичен такому методу угадывания: «это число равно 1? это число равно 2? это число равно 3?... ” – и так до тех пор, пока удастся угадать.
Понятно, что такой метод угадывания далеко не самый быстрый. Если спросить «больше ли заданное число, чем 512?» (512 = 1024/2), то независимо от ответа мы сужаем границы поиска в два раза (т. е. должны искать либо от 1 до 512, либо от 513 до 1024). Так же и дальше; например, если известно, что искомое число лежит в границах от 513 до 1024, то вопрос должен быть таким: «больше ли заданное число, чем 768?» (768 = 512 + (1024 – 512)/2).
Поиск в упорядоченном массиве аналогичен описанному методу угадывания. Есть небольшая разница: мы выбираем для сравнения не «средний по значению» элемент (мы же не знаем его индекс), а «средний по номеру». Такой алгоритм поиска называется дихотомией (делением пополам). Важно отметить, что здесь мы впервые сталкиваемся с одним из алгоритмов, объединяемых общим названием «разделяй и властвуй» (см. также метод сортировки массива QuickSort в разделе 5.2. [6])
Комментарии к функции Дихотомия. В процессе работы искомое значение всегда находится на отрезке между элементами с индексами Левый и Правый. Собственно деление пополам – вычисление индекса Средний, равного их полусумме, и формирование нового отрезка для поиска, имеющего в 2 раза меньшую длину (границы нового отрезка - либо Левый и Средний, либо Средний+1 и Правый).
function Дихотомия (Граница,ИскомыйКлюч: word): word;
var Левый,Правый,Средний: word;
begin
if Массив[Граница].Ключ<=ИскомыйКлюч
then begin Дихотомия:=0; exit; end;
Левый:=1; Правый:=Граница;
while Левый<Правый do begin
Средний:=(Левый+Правый) div 2; {вот дихотомия!}
if Массив[Средний].Ключ<=ИскомыйКлюч
then Левый:=Средний+1
else Правый:=Средний;
end;
Дихотомия:=Правый;
end;
Функция специально написана таким образом, чтобы она возвращала наименьший из номеров элементов, для которых выполнено условие Ключ>ИскомыйКлюч (т.е. здесь алгоритм находит первый «больший» элемент, ср. с функцией из предыдущего раздела). Это сделано не столько для демонстрации разных вариантов возврата (также см. предыдущий раздел), сколько для того, чтобы эту функцию можно было применить в качестве вспомогательного алгоритма в разделе 4.1. Отметим также, что оператор Левый:=Средний+1 нельзя заменить на Левый:=Средний, иначе выполнение алгоритма может зациклиться.
Оценка эффективности обоих рассмотренных методов поиска крайне проста. Для линейного поиска получаем эффективность ~n – как «в среднем», так и «в худшем». А для дихотомии эффективность «в худшем» пропорциональна log2n – поскольку можно построить двоичное дерево, содержащее n вершин, глубина которого будет равной [log2n] [7]. С помощью несложных вычислений можно убедиться, что эффективность «в среднем» для дихотомии также ~logn. Эти вычисления вряд ли представляют интерес для тем «Поиск» и «Сортировка», поэтому здесь они не приведены.