Binäre Suche

[sx2008]

Zitat von Apollonius:

Sollten das nicht eher Klassenmethoden sein?

Im Moment vielleicht schon; die Klasse TBSearch hat z.Zt. nur die Aufgabe den Code zusammenzuhalten.
Aber das könnte sich ändern.
Das Grundlegende an der Binären Suche ist doch, dass ein beliebiges Element aus einem Array mit einem Schlüssel verglichen wird.
Diesen Vergleich könnte man in eine virtuelle Methode auslagern, so dass der Algorithmus für alle denkbaren Datentypen erweiterbar ist.
Die Basisklasse sieht dann so aus (ungetestet):

Delphi-Quellcode:

TBSearch = class(TObject)
  private
    FSorted : Boolean;
  protected
    FLeft  : Integer;   // untere Grenze der Daten (meist 0)
    FRight : Integer;   // obere Grenze der Daten
    // Rückgabewert von KeyCompare()
    // Key < daten[index]  => -1  (negative Zahl)
    // Key = daten[index]  =>  0
    // Key > daten[index]  => +1  (positive Zahl)
    function KeyCompare(index:integer):integer;virtual;abstract;   
  public
    procedure QuickSort(Start, Stop: Integer);
    function Search: Integer; overload;
    function Search(out found:TBFound): Integer; overload;
    property Sorted : Boolean read FSorted;
  end;

Für jeden Datentyp, nach dem man suchen möchte, muss eine eigene Klasse abgeleitet werden.
Hier ein Beispiel für Integer:

Delphi-Quellcode:

TIntArray = array of Integer;
TBSearchInteger = class(TBSearch)
private
   FData : TIntArray;
   procedure SetData(const value:TIntArray);
protected
   function KeyCompare(index:integer):integer;override;
public
   Key : Integer;  // der Wert nach dem gesucht werden soll
   property Data : TIntArray read FData write SetData(value:TIntArray);  // die Daten
end;

procedure TBSearchInteger.SetData(const value:TIntArray);
begin
  FLeft := Low(value);   // untere 
  FRight:= High(value);  // und obere Grenze merken
  FData := value;
end;

function TBSearchInteger.KeyCompare(index:integer):integer;
begin
  if Key < FData[index] then Result := -1
  else if Key > FData[index] then Result := 1
  else Result := 0;
  // möglich wäre auch: Result := Key - FData[index]
end;

Jetzt ergibt sich aber das Problem, das Quicksort nicht mehr funktioniert,
denn Quicksort hat zwei Grundoperationen: Vergleichen und Tauschen.
Also brauchen wir zwei weitere virtuelle Methoden in der Basisklasse:

Delphi-Quellcode:

function Compare(a,b:integer):integer;virtual;abstract;  // vergleiche Element A mit B
procedure Exchange(a,b:integer);virtual;abstract; // tausche Element A mit B

Das war jetzt vielleicht ein bißchen viel auf einmal, drum höre ich jetzt auf. 8)