Binäre Suche

[alzaimar]

Der erweiterte Parameter Found wird so nicht benötigt. Es reicht, TRUE bzw. FALSE zu liefern sowie die Position, VOR der das Element eingefügt werden kann. Dieser Wert liegt zwischen Low(Array) bis High(Array)+1. So steht es jedenfalls in der Literatur... In meiner BTree-Klasse verwende ich folgenden Code;

Delphi-Quellcode:

function Search(const aItem: TElement; AArray: TElementArray; var aIndex: Integer): Boolean;
var
  L, R, M: integer; // Für Left, Right, Middle

begin
  L := Low(AArray);
  R := High(AArray);
  while (L <= R) do begin
    M := (L + R) div 2;
    case CompareItems(aItem, AArray[M]) of
      coComparedLess:
        R := M - 1;
      coComparedEqual: begin
          Result := True;
          aIndex := M;
          Exit;
        end;
      coComparedGreater:
        L := M + 1
    end;
  end;
  aIndex := L;
  Result := False;
end;

Die Funktion liefert TRUE sowie in aIndex die Position, wenn das Element aItem in AArray gefunden wurde bzw FALSE, wenn das Element nicht gefunden wurde. In diesem Fall bezeichnet aIndex die Position, an der das Element im AArray eingefügt werden könnte.

[edit] Code korrigiert [/edit]