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

Листинг 4.7. Последовательный поиск в отсортированном массиве TList

function TDTListSortedIndexOf(aList : TList; aItem : pointer;

aCompare : TtdCompareFunc) : integer;

var

Inx, CompareResult : integer;

begin

{искать первый элемент больший или равный элементу aItem}

for Inx := 0 to pred(aList.Count) do begin

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

if (CompareResult >= 0) then begin

if (CompareResult = 0) then

Result := Inx

else

Result := -1;

Exit;

end;

end;

{если мы попали сюда, значит искомый элемент не найден}

Result := -1;

end;

Обратите внимание, что функция сравнения вызывается только один раз при каждом выполнении цикла. Мы не знаем, что делает функция aCompare - для нас это "черный ящик". Следовательно, желательно ее вызывать как можно реже. Поэтому при каждом выполнении цикла мы вызываем ее только один раз и сохраняем полученный результат в переменной целого типа. После этого переменную можно использовать сколько угодно раз, не вызывая функцию.

Как уже говорилось, приведенная функция поиска нисколько не увеличивает скорость обнаружения искомого элемента, если искомый элемент присутствует в массиве (в среднем, как и ранее, для этого потребуется провести n/2 сравнений). Единственным ее преимуществом перед предыдущей функцией является то, что при отсутствии искомого элемента в массиве результат будет получен быстрее. Скоро мы рассмотрим алгоритм бинарного поиска, который позволит повысить быстродействие в обоих случаях.

В связных списках последовательный поиск выполняется точно так же, как и в массивах. Тем не менее, элементы проходятся не по индексу, а по указателю Next. Для класса TtdSingleLinkList, описанного в главе 3, можно разработать две следующих функции: первая - для выполнения поиска по несортированному связному списку, и вторая - по отсортированному. Функции просто указывают, найден ли искомый элемент. В случае, если элемент найден, список будет установлен в позицию искомого элемента. В функции для отсортированного списка курсор будет установлен в позицию, где должен находиться искомый элемент, чтобы список оставался отсортированным.

Листинг 4.8. Последовательный поиск в однонаправленном связном списке

function TDSLLSearch(aList : TtdSingleLinkList;

aItem : pointer;

aCompare : TtdCompareFunc) : boolean;

begin

with aList do begin

MoveBeforeFirst;

MoveNext;

while not IsAfterLast do begin

if (aCompare(Examine, aItem) = 0) then begin

Result := true;

Exit;

end;

MoveNext;

end;

end;

Result := false;

end;

function TDSLLSortedSearch(aList : TtdSingleLinkList;

aItem : pointer;

aCompare : TtdCompareFunc) : boolean;

var

CompareResult : integer;

begin

with aList do begin

MoveBeforeFirst;

MoveNext;

while not IsAfterLast do begin

CompareResult := aCompare(Examine, aItem);

if (CompareResult >= 0) then begin

Result := (CompareResult = 0);

Exit;

end;

MoveNext;

end;

end;

Result := false;

end;

Соответствующие функции для класса TtdDoubleLinkList будут точно такими же.

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

Алгоритм бинарного поиска применим только для отсортированных контейнеров.

Предположим, что у нас имеется отсортированный массив. Как было показано ранее, алгоритм последовательного поиска даже при использовании выхода из цикла в случае отсутствия в списке искомого элемента принадлежит к классу O(n). Каким образом можно улучшить быстродействие?

Ответом может служить бинарный поиск. Он основан на стратегии "разделяй и властвуй": начинаем с большой проблемы, разбиваем ее на маленькие проблемы, которые легче решить, а, затем, следовательно, решаем всю большую проблему.

Бинарный поиск работает следующим образом. Берем средний элемент массива. Равен ли он искомому элементу? Если да, то поиск успешно завершен. В противном случае, если искомый элемент меньше среднего, то можно сказать, что, если элемент присутствует в массиве, он находится в первой половине. С другой стороны, если искомый элемент больше среднего, он должен находиться во второй половине. Таким образом, одним сравнением мы разбили нашу проблему на две части. Теперь мы применяем тот же алгоритм к выбранной части массива: находим средний элемент и определяем, в какой половине (точнее уже в четвертой части) находится искомый элемент. Мы снова делим проблему на две части. Описанные операции продолжаются до тех пор, пока искомый элемент не будет найден (разумеется, если он присутствует в массиве).

Это и есть алгоритм бинарного поиска. Поскольку размер массива при каждом выполнении цикла уменьшается в два раза, быстродействие алгоритма будет выражаться как O(log(n)), т.е. скорость работы алгоритма примерно пропорциональна функции двоичного логарифма log(_2_) от количества элементов в массиве (таким образом, возведение количества элементов массива во вторую степень приведет к увеличению времени поиска только в два раза).