Binäre Suche rekursiv

[CalganX]

Hi,
ich versuche gerade just for fun eine binäre Suche zu programmieren, doch irgendwie funktioniert bei mir die Rekursion nicht richtig.

Delphi-Quellcode:

type
  TEntry = record
    n_name: string;
    v_name: string;
  end;
  TList = array[1..lg] of TEntry;

function binsuche(nname: string; list: TList; index: integer): integer;
var
  tdx: integer;
begin
  if list[index].n_name = nname then begin
    Result := index;
    Exit;
  end;

  if list[index].n_name > nname then
    tdx := index div 2
  else
    tdx := (index + lg) div 2;

  if tdx <> index then
    Result := binsuche(nname, list, tdx)
  else
    Result := -1;
end;

Ich habe ein Testfeld mal recht willkürlich belegt:

Delphi-Quellcode:

procedure belege(var list: TList);
begin
  List[1].n_name := 'Adams';
  List[1].v_name := 'Douglas';

  List[2].n_name := 'Bauer';
  List[2].v_name := 'Joachim';

  List[3].n_name := 'Daniels';
  List[3].v_name := 'Jack';

  List[4].n_name := 'Gorbatschow';
  List[4].v_name := 'Michail';

  List[5].n_name := 'Müller';
  List[5].v_name := 'Karl-Otto';
end;

Wenn ich nun nach dem fünften Eintrag suche (Müller), dann findet meine binäre Suche keinen Eintrag. Woran kann das liegen?

Chris

[marabu]

Hallo Chris,

die Signatur deiner Funktion ist falsch, du musst die upper und die lower bound für die zu untersuchende Liste übergeben. Im Rumpf vergleichst du mit dem mittleren Element der Liste und veränderst die entsprechende Grenze, wenn die Suche noch nicht erfolgreich war. Das Abbruchkriterium ist dann lBound > uBound.

Viel Spaß

marabu

[hoika]

Hallo,

just gestern habe ich es doch mal geschafftm
meine BinSearch fertigzustellen.

Sie arbeitet mit TList, aber abgesehen von der Start-Grenze 0,
sollte es doch auch so klappen.

Das ganze sieht etwas komplizierter aus als Code aus dem Netz,
z.B. das

Delphi-Quellcode:

iCompareResult:= BusinessObject.Compare(
  theSearchBusinessObject, theSearchMethod);

Hintergrund ist, dass die BinSearch verschiedene Suchkriterien hat.
Natürlich muss die Liste vorher nach dem jeweiligen Koriteriem sortiert werden.

Das TBusinessObject ist mein Basisobjekt, was eine abstrakte Compare-Methode enthält.

Delphi-Quellcode:

{
 name:
   InternalBinSearch
 usage:
   internal bin search method
 parameter:
   theLow          - low order
   theHigh         - high order
   theSearchMethod - search method
 return parameter:
 return:
   NIL, if not found
 notes:
}
function TBusinessObjectList.InternalBinSearch(
  const theLow, theHigh: Integer;
  const theSearchBusinessObject: TBusinessObject;
  const theSearchMethod: Integer): TBusinessObject;
var
  iMiddle        : Integer;
  iNewLow        : Integer;
  iNewHigh       : Integer;
  iCompareResult : Integer;
  BusinessObject : TBusinessObject;
begin
  Result:= NIL;

  if theLow>theHigh then Exit;

  iMiddle:= theLow + ((theHigh-theLow) div 2);

  BusinessObject:= Items[iMiddle];
  iCompareResult:= BusinessObject.Compare(
    theSearchBusinessObject, theSearchMethod);

  if iCompareResult=0 then
  begin
   { we got it :) }
    Result:= BusinessObject;
    Exit;
  end;

  if iCompareResult=-1 then
  begin
   { if the current object is smaller than we need
     we continue searching at the right side (the higher side) }
    iNewLow  := iMiddle+1;
    iNewHigh := theHigh;
  end
  else
  begin
   { if the current object is smaller than we need
     we continue searching at the right side (the higher side) }
    iNewLow  := theLow;
    iNewHigh := iMiddle-1;
  end;

  Result:= InternalBinSearch(iNewLow, iNewHigh,
    theSearchBusinessObject, theSearchMethod);
end;  { TBusinessObjectList.InternalBinSearch }

Der Aufruf erfolgt über

Delphi-Quellcode:

{
 name:
   BinSearch
 usage:
   internal bin search method
 parameter:
   theLow          - low order
   theHigh         - high order
   theSearchMethod - search method
 return parameter:
 return:
   NIL, if not found
 notes:
}
function TBusinessObjectList.BinSearch(
  theSearchBusinessObject: TBusinessObject;
  const theSearchMethod: Integer): TBusinessObject;
begin
  Result:= InternalBinSearch(0, Count-1,
    theSearchBusinessObject, theSearchMethod);
end;  { TBusinessObjectList.BinSearch }

Heiko

[CalganX]

Hi marabu,

danke für den Tipp. Mein Code sieht jetzt so aus:

Delphi-Quellcode:

function binsuche(nname: string; list: TList; lbound, ubound: integer): integer;
var
  tdx: integer;
begin
  if lbound > ubound then begin
    Result := -1;
    Exit;
  end;  

  tdx := lbound + ( (ubound - lbound) div 2 );

  if list[tdx].n_name = nname then begin
    Result := tdx;
    Exit;
  end;

  if list[tdx].n_name > nname then
    Result := binsuche(nname, list, 1, tdx)
  else
    Result := binsuche(nname, list, tdx, ubound);
end;

Wenn ich nun nach dem letzten Element der Liste suche, bekomme ich einen Stack Overflow um die Ohren gehauen und das Programm beendet sich (ist ein Konsolenprogramm).

@hoika: Danke, ich guck mir den Code mal an und vergleiche und versuche den Fehler zu finden.

Chris


Edit:
Fehler schon gefunden.
Ich habe die Rekursionsgrenzen etwas verändert:

Delphi-Quellcode:

  if list[tdx].n_name > nname then
    Result := binsuche(nname, list, 1, tdx-1)
  else
    Result := binsuche(nname, list, tdx+1, ubound);

So funktioniert's. Danke für eure Hilfe.

[marabu]

Chris,

du solltest noch etwas sorgfältiger testen. Bei der binären Suche veränderst du die obere oder die untere Grenze - eine konstante untere Grenze 1 sieht irgendwie sehr willkürlich aus.

Delphi-Quellcode:

if list[tdx].n_name > nname 
  then Result := binsuche(nname, list, lBound, Pred(tdx))
  else Result := binsuche(nname, list, Succ(tdx), uBound);

Und zumindest für die Suche eines Strings könntest du die Funktion noch verallgemeinern.

Gute Nacht

marabu

[CalganX]

Hi marabu,

Zitat von marabu:

du solltest noch etwas sorgfältiger testen. Bei der binären Suche veränderst du die obere oder die untere Grenze - eine konstante untere Grenze 1 sieht irgendwie sehr willkürlich aus.

Stimmt, jetzt wo du's sagst.

Zitat:

Und zumindest für die Suche eines Strings könntest du die Funktion noch verallgemeinern.

Naja, es ging mir jetzt primär darum zu gucken, warum ich das in meiner Info-Klausur nicht richtig gemacht habe (das regt mich schon den ganzen Tag auf, dass mir das meine 15 Punkte versaut hat ). Und da war es halt dieses Verzeichnis.
Verallgemeinern kann man das sicher noch... Aber spätestens wenn es darum geht, für einen Vergleich, einen Methodenzeiger auf eine Callback-Funktion zu setzen, denke ich sollte es erstmal reichen. Und an dieser Stelle reicht es mir auch erstmal.

Danke für deine Hilfe,
Chris