Binärsuche

[Nexus]

Bist du sicher, dass sie nicht wahr wird? Ist das kurz vor der Rückgabe an den Aufrufer von binsearch() ? Versuch ansonsten mal, die Bedingung zu speichern:

bool ret = (arr[iMitte] == srch);

[freakC++]

Naja, wenn die Bedingung wahr wäre, dann würde sofort "true" zurückgegeben werden. Das ist aber nicht der Fall. Ich versuche aber mal den Wert zu speichern.

lg, freakC++

[Nexus]

freakC++ schrieb:

Naja, wenn die Bedingung wahr wäre, dann würde sofort "true" zurückgegeben werden. Das ist aber nicht der Fall.

Das sollte aber auch nicht der Fall sein, wenn der Algorithmus korrekt läuft, oder? Von welchem Zeitpunkt sprechen wir eigentlich? In deinem Kommentar stand "zum Schluss 501", darum bin ich davon ausgegangen, dass es sich um die Rekursion unmittelbar vor der Rückgabe handelte.

[freakC++]

Hallo,
wenn ich in "if(arr[iMitte]==srch)" noch eine Ausgabe schreibe, dann wird diese ausgegeben. Das bedeutet, dass die Bedingung erfüllt ist. Warum wird dann trotzdem "false" ausgegeben? Das verstehe ich einfach nicht.

Mmmh, wenn ich jedoch den else if Zwei

else if(iMitte==0) return false;

umschreibe zu:

else if(iMitte==0) cout << "HÄÄÄ";

dann wird nicht "HÄÄÄ" ausgegeben. Das bedeutet auch, dass das false nicht aus dieser Bedingung kommt. Woher kommt es dann? Und warum wird nicht true zurückgegeben, obwohl die Bedingung wahr ist.

Vielen Dank
lg, freakC++

[Nexus]

Kannst du den aktuellen Code posten mit allen relevanten Variablenwerten, die du im Debugger gesehen hast und den Werten, die du erwartest? Ich kann dein Problem sonst nicht nachvollziehen.

Du debuggst schon im Debug-Modus, oder?

[keksdoze]

reichst du den rückgabewert auch weiter? in deinem beispiel hast du
die funktion nur aufgerufen, und den rückgabewert ignoriert.

versuch mal

[cpp]

if(arr[iMitte] < srch)
return binsearch(arr,iMitte,iEnd,srch);
else
return binsearch(arr,iBegin, iMitte,srch);
[cpp]

[freakC++]

Hallo,
das mit der Weitergabe ist wohl ein Fehler. Nun wird "true" ausgeben, doch wenn ich nach einem nichtvorhandenen Element suche, kommt es zum StackOverFlow. Liegt das an der abbruchbedingung. Ich habe die zu

else if(iMitte<0) 
 return false;

geändert, doch das bringt auch nichts.

vielen Dank für die Hilfe
lg, freakC++

[volkard]

Die Binäre Suche ist viel zu fallenreich, um sie durch Versuch und Irrtum zu lösen, fürchte ich.

[ghlo]

else if(iMitte==0||iMitte==iEnd-1)

[freakC++]

Trotzdem würde ich mein Problem gerne lösen. Ich bin einen kleinen Schritt weiter, nämlich, dass iMitte ja auch hier größer werden kann.

Irgendwie muss die Abbruchbedingung geändert werden, doch ich komm einfach nicht auf die richtige Lösung.

Vielen Dank für die Hilfe
lg, freakC++

[freakC++]

Ha, es funktioniert. Das ist die richtige Abbruchbedingung. DAAnke! Super! Ich wusste, dass es irgendwie daran liegen muss.

Noch eine letzte Frage: warum heißt das eigentlich "Binäre Suche"? Weil das Array aufgeteilt wird?? Hier ist doch nichts binär!

Vielen Dank, ghlo (und natürlich auch alle anderen)
lg, freakC++

[Nexus]

freakC++ schrieb:

Noch eine letzte Frage: warum heißt das eigentlich "Binäre Suche"? Weil das Array aufgeteilt wird?? Hier ist doch nichts binär!

Das Array wird rekursiv in zwei Teile aufgeteilt, deshalb binär. Der Begriff "binär" hat nicht nur mit Zahlensystemen zu tun.

[ghlo]

http://de.wikipedia.org/wiki/Bin%C3%A4rbaum

[freakC++]

Achso, dann war das bei mir ein Missverständis. Das ist jedoch jetzt behoben!

Danke
lg, freakC++