Джулиан Бакнелл - Фундаментальные алгоритмы и структуры данных в Delphi

Ниже приведен пример выполнения бинарного поиска в массиве TList (функцию можно найти в файле TDTList.pas на Web-сайте издательства, в разделе сопровождающих материалов).

Листинг 4.9. Бинарный поиск в отсортированном массиве TList

function TDTListSortedIndexOf(aList : TList; aItem : pointer;

aCompare : TtdCompareFunc) : integer;

var

L, R, M : integer;

CompareResult : integer;

begin

{задать значения для индексов первого и последнего элементов}

L := 0;

R := pred(aList.Count);

while (L <= R) do begin

{вычислить индекс среднего элемента}

M := (L + R) div 2;

{сравнить значение среднего элемента с искомым значением}

CompareResult := aCompare(aList.List^[M], aItem);

{если значение среднего элемента меньше искомого значения, переместить левый индекс на позицию до среднего индекса}

if (CompareResult < 0) then

L := succ(M)

{если значение среднего элемента больше искомого значения, переместить правый индекс на позицию после среднего индекса}

else if (CompareResult > 0) then

R := pred(M)

{в противном случае искомый элемент найден}

else begin

Result := M;

Exit;

end;

end;

Result := -1;

end;

Для описания подмассива, рассматриваемого в текущий момент, используются две переменных - L и R, которые хранят, соответственно, левый и правый индексы. Первоначально значения этих переменных устанавливаются равными 0 (первый элемент массива) и Count-1 (последний элемент массива). Затем мы входим в цикл While, из которого выйдем после обнаружения в массиве искомого элемента или когда значение переменной L превысит значение переменной R, что означает, что искомый элемент в массиве отсутствует. При каждом выполнении цикла вычисляется индекс среднего элемента (фактически это среднее значение между L и R). Затем значение элемента со средним индексом сравнивается с искомым значением. Если значение среднего элемента меньше, чем искомое, мы переносим левый индекс на позицию после среднего. В противном случае мы переносим правый индекс на позицию перед средним. Таким образом, мы определяем новый подмассив для поиска. Если же значение среднего элемента равно искомому, поиск завершен.

Для примера на рис. 4.1 приведены шаги, выполняемые при бинарном поиске буквы d в отсортированном массиве, содержащем буквы от a до k. На шаге (а) переменная L указывает на первый элемент (индекс 0), а R - на последний (индекс 10). Это означает, что значение переменной M будет составлять 5. Далее мы выполняем сравнение: значение элемента с индексом 5 равно f, а это больше искомого значения d.

Рисунок 4.1. Бинарный поиск в массиве

Согласно алгоритму, мы устанавливаем значение R равным M-1 (таким образом, правая граница подмассива теперь находится слева от среднего элемента). Это означает, что значение R теперь равно 4. Новое значение среднего индекса будет равно 2, как показано на шаге (b). Выполняем сравнение: буква c (значение элемента с индексом 2) меньше, чем d.

Теперь, в соответствии с алгоритмом, необходимо установить индекс L за индексом M (т.е. M+1 или 3). Новое значение переменной M на шаге (с) равно 3. Выполняем сравнение: элемент с индексом 3 содержит букву d, а это и есть наше искомое значение. Поиск завершен.

Изучая код листинга 4.9, можно придти к выводу, что маловероятно, чтобы бинарный поиск использовался для связных списков, если, конечно, не воспользоваться индексным доступом к элементам списка, который, как уже упоминалось в главе 3, приводит к снижению быстродействия.

Но, тем не менее, реализация бинарного поиска для связных списков оказывается не такой уж и неразрешимой проблемой. Во-первых, нужно понимать, что в общем случае переход по ссылке выполняется гораздо быстрее, нежели вызов функции сравнения. Следовательно, можно сказать, что переход по ссылке - это "хорошо", а вызов функции сравнения - "плохо". Это означает, что следует стремиться к минимизации вызовов функции сравнения. (Поскольку для нас функция сравнения - "черный ящик", мы не можем сказать, сколько времени требуется на ее выполнение: много или мало, по крайней мере, по сравнению со временем, требуемым на переход по ссылке.) Во-вторых, необходимо иметь доступ к "внутренностям" связного списка.

Давайте рассмотрим принцип организации бинарного поиска на примере ­обобщенного связного списка, а затем рассмотрим код для классов TtdSingleLinkList и TtdDoubleLinkList. Для нашего обобщенного связного списка должно быть известно количество содержащихся в нем элементов, поскольку оно понадобится при реализации алгоритма бинарного поиска. Кроме того, будем считать, что связный список содержит фиктивный начальный узел.