Hi,
ich habe ein Problem bei meiner Binärsuche. Ich habe ein Array
daten: array[0..n] of integer;. Nun sagen wir mal
n := 10 und ich suche nach der 5. Dann erhalte ich als Ergebnis, dass die 5 nicht vorhanden ist, obwohl ich weiß, dass die 5 vorhanden ist.
Hier der Aufbau des arrays und der restlichen Globalen Variablen:
Delphi-Quelltext
1: 2: 3: 4:
| const max :integer = 100;var daten: array of integer; log:boolean; erg:integer; |
So wird das Array gefüllt und angezeigt:
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15:
| procedure TForm1.FormCreate(Sender: TObject); var i : integer; begin randomize; for i:= 0 to random(max) do begin SetLength(daten, i+1); daten[i]:=i+1; end; for i := 0 to high(daten) do memo1.lines.add(inttostr(daten[i])); end; |
Nun zu dem Teil, der die suche startet:
Um zu überrüfen ob die Zahl gefunden wurede oder nicht, hänge ich die Zahl an das Ende des arrays, das sieht so aus:
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10:
| procedure TForm1.Button1Click(Sender: TObject); var ergebnis,suche,max:integer; begin suche:=strtoint(edit1.Text); setLength(daten,high(daten)+2); max:=high(daten); daten[max] := suche; |
So nun starte ich die suche mit:
Delphi-Quelltext
1: 2: 3:
| ergebnis:=search(suche,0,max); |
Also wird diese Prozedur aufgerufen, mitder ich rekursiv suche:
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14:
| function search(suche,links,rechts:integer):integer; var mitte:integer; begin mitte:= (links + rechts) div 2; if daten[mitte] = suche then begin search:= mitte; erg:=mitte; end else If daten[mitte] < suche then search(suche,mitte+1,rechts) else search(suche,links,mitte-1); end; |
So, die Auswertung mache ich am ende so: (+ das löschen der letzten Zahl)
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9:
| if erg = max then label1.Caption:='Die Zahl '+inttostr(suche)+' wurde nicht gefunden !' else label1.Caption:='Die Zahl '+inttostr(suche)+' wurde gefunden !'+#13+'Sie befindet sich an Position '+inttostr(erg);
setlength(daten,max); end; |
SO nun habe ich in der Rekursion etwas markiert. Hier ist das eigentliche Problem. Ich weise der Funktion ein Ergebnis zu, nämlich die richtige Position. Im Compiler steht da auch die rcihtige Position der 5, nämlich 4.
Bei der Auswertung allerding bekommt die Variable
ergebnis den letzten Wert des Arrays zugewiesen. Daraus folgt, dass das Programm sagt, dass die Zahl nicht gefunden wurde, obwol die Rekursion das richtige Ergebis hat. Deswegen verwende ich zZt. eine Hilfvariable (
erg).
Warum liefert mir die Rekursion nicht das korrekte Ergebnis? warum muss ich diesen "Umweg" gehen?
kann mir jemand evtl n Tipp geben?
danke, hibbert.