(т.е. значение ListCount, деленное на два и округленное до целого). Переходим по ссылке от узла BeforeList на один шаг и находим искомый узел.
Если вы считаете, что в процессе выполнения алгоритма искомый узел был пройден несколько раз, то вы совершенно правы. Но следует иметь в виду, что вызов функции сравнения может быть намного медленнее, чем переход по ссылкам (например, если элементы списка представляют собой строки длиной 1000 символов, то для определения соотношения между строками функции сравнения придется сравнить в среднем 500 символов). Если бы связный список содержал целые числа, а мы отказались бы от частого использования функции сравнения, то быстрее всех оказался бы алгоритм последовательного поиска.
Ниже приведена функция бинарного поиска для класса TtdSingleLinkList.
Листинг 4.10. Бинарный поиск в отсортированном однонаправленном связном списке
function TtdSingleLinkList.SortedFind(aItem : pointer;
aCompare : TtdCompareFunc) : boolean;
var
BLCursor : PslNode;
BLCursorIx : longint;
WorkCursor : PslNode;
WorkParent : PslNode;
WorkCursorIx : longint;
ListCount : longint;
MidPoint : longint;
i : integer;
CompareResult :integer;
begin
{подготовительные операции}
BLCursor := FHead;
BLCursorIx := -1;
ListCount := Count;
{пока в списке имеются узлы...}
while (ListCount <> 0) do begin
{вычислить положение средней точки; оно будет не менее 1}
MidPoint := (ListCount + 1) div 2;
{переместиться вперед до средней точки}
WorkCursor := BLCursor;
WorkCursorIx := BLCursorIx;
for i := 1 to MidPoint do begin
WorkParent := WorkCursor;
WorkCursor := WorkCursor^.slnNext;
inc(WorkCursorIx);
end;
{сравнить значение узла с искомым значением}
CompareResult := aCompare(WorkCursor^.slnData, aItem);
{если значение узла меньше искомого, уменьшить размер списка и повторить цикл}
if (CompareResult < 0) then begin
dec(ListCount, MidPoint);
BLCursor := WorkCursor;
BLCursorIx := WorkCursorIx;
end
{если значение узла больше искомого, уменьшить размер списка и повторить цикл}
else if (CompareResult > 0) then begin
ListCount := MidPoint - 1;
end
{в противном случае искомое значение найдено; установить реальный курсор на найденный узел}
else begin
FCursor := WorkCursor;
FParent := WorkParent;
FCursorIx := WorkCursorIx;
Result := true;
Exit;
end;
end;
Result := false;
end;
Функция бинарного поиска для класса TtdDoubleLinkList аналогична приведенной функции.
Вставка элемента в отсортированный контейнер
Если необходимо создать отсортированный массив или связный список, у нас существует выбор того или иного метода поддержания порядка элементов. Можно сначала вставлять элементы в контейнер, а затем их сортировать и сортировать содержимое контейнера при вставке каждого нового элемента, или же при выполнении вставки находить позицию, вставив новый элемент в которую контейнер останется отсортированным. Если предполагается, что контейнер будет часто использоваться в отсортированном виде, тогда имеет смысл при вставке сохранять правильный порядок элементов.
В таком случае наша задача сводится к вычислению положения нового элемента в отсортированном списке. После определения позиции мы просто вставляем в нее новый элемент. Ранее говорилось, что последовательный поиск может помочь определить точку вставки, но, к сожалению, быстродействие последовательного поиска достаточно низкое. Можно ли для определения точки вставки воспользоваться бинарным поиском?
Оказывается, можно. Посмотрите внимательно на реализацию бинарного поиска для массива, приведенную в листинге 4.9. Когда выполнение цикла завершается, и искомый элемент не найден, что можно определить на основании значений переменных L, R и M? Во-первых, очевидно, что L>R. Рассмотрим, что происходит при выполнении цикла в последний раз. В начале цикла мы должны были иметь L=R или L=R-1. При этом вычисление даст, что M=L. Если бы разница между L и R была больше, скажем, L=R-2, тогда значение M попало бы в диапазон между L и R, и цикл был бы выполнен, по крайней мере, еще один раз.
Если при выполнении цикла в последний раз искомый элемент был меньше, чем элемент в позиции M, то переменная R получила бы значение M-1, и цикл завершился бы. Мы уже знаем, что искомого значения не было до элемента M, поэтому можно сделать вывод, что новый элемент должен быть вставлен между элементами M-1 и M. Другими словами, мы вставляем элемент в позицию M.
С другой стороны, если бы искомый элемент был больше элемента в позиции M, то переменная L получила бы значение M+1. В этом случае можно принять, что в начале цикла L=R. В противном случае цикл был бы выполнен еще один раз. Мы уже знаем, что искомого значения не было после элемента M, поэтому можно сделать вывод, что новый элемент должен быть вставлен между элементами M и M+1. Другими словами, мы вставляем элемент в позицию M+1.
Таким образом, новый элемент должен вставляться в позицию M или M+1 в зависимости от того, что произошло при последнем выполнении цикла. Но давайте подумаем еще раз. Разве между описанными
