Binärsuche

freakC++

Hey,
leutz, ich werde mich bemühen. Ok, ich schaue nochmal drüber. Es halt so, dass ich keinen anderen als euch habe, den ich fragen kann. Dennoch schaue ich noch mal drüber und belästige euch dann erst wieder mit fragen

Vielen Dank dennoch
lg, freakC++

freakC++

Hallo zusammen,
so nach anfänglicher Kritik, habe ich auf irgendwelchen Pseudocodekram verzichtet und nochmal von vorne angefangen. Ich habe mich dann auch entschieden hier gleich rekursiv dranzugehen. Ich habe mich also bemüht und auch den Debugger genutzt, wie Nexus gefordert hat (er hat ja recht) . Trotzdem brauche ich Hilfe, da das Ergebnis falsch ist.

bool binsearch(int* arr, int iBegin, int iEnd, int srch)
{
	int iMitte = (iBegin + iEnd)/2;
	if(arr[iMitte]==srch)
		return true;
	else if(iMitte==0) return false;
	if(arr[iMitte] < srch)
		binsearch(arr,iMitte,iEnd,srch);
	else 
		binsearch(arr,iBegin, iMitte,srch);
}
int main() 
{ 
	int arr[1000];
	for (int i=0; i < 1000; ++i)
		arr[i]=i;

    cout <<  boolalpha << binsearch(arr,0,1000,501) << endl;    
}

Für alle Werte außer 500 (das ist klar), wird false ausgegeben. In diesem Beispiel müsste aber true ausgegeben werden. Woran liegt das?

Vielen Dank für eure stetige Hilfe
lg, freakC++

freakC++

Sach mal bin ich dumm?

Ich habe nochmal ein bisschen rumgespielt. Es wird richtig aufgeteilt und es kommt immer das richtige raus, doch irgendwie wird trotzdem die erste if Bedingung nicht wahr:

bool binsearch(int* arr, int iBegin, int iEnd, int srch)
{
	int iMitte = (iBegin + iEnd)/2;
	cout << arr[iMitte] << endl; //zum Schluss 501
	cout << "Search " << srch << endl; //immer 501
	if(arr[iMitte]==srch) //warum ist diese bedingung dann nicht wahr?
		return true;
...

Ich brauche eure Hilfe
lg, freakC++

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?

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.

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.

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++