{искать первый элемент больший или равный элементу 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;