Binäre Suche

[sx2008]

Wenn das Element nicht gefunden wurde, wäre es sinnvoll, den Index des nächst-kleineren Elements zurückzuliefern.
Wenn man dieses Element dann in das Array oder Liste einfügen möchte, dann kennt man die Einfügestelle und muss nicht neu sortieren.

Allerdings braucht man dann einen zusätzlichen Var- oder out-Parameter (boolean), um das Flag found zurückzugeben.
Mit überladenden Funktionen kann man Beides haben:

Delphi-Quellcode:

TBSearch = class(....
 function Search(IntArray: TIntArray; x: Integer; Sorted: Boolean; Out found:boolean): Integer;overload;
 function Search(IntArray: TIntArray; x: Integer; Sorted: Boolean): Integer;overload;
...
function TBSearch.Search(IntArray: TIntArray; x: Integer; Sorted: Boolean): Integer;
var
  found : Boolean;
begin
  result := Search(IntArray, x, Sorted, found);
  if not found then Result := -1;
end;

Dann muss man sich noch Gedanken machen, was passiert, sollte der Suchschlüssel kleiner als das erste Arrayelement oder grösser als das letzte Arrayelement sein.
Man müsste dazu den Parameter found umdefinieren:

Delphi-Quellcode:

type
  TBSFound = (bsFound {gefunden}, bsNotFound {nicht gefunden}, bsLower, bsHigher);
...
 function Search(IntArray: TIntArray; x: Integer; Sorted: Boolean; Out found:TBSFound): Integer;overload;