Binärsuche Fehlersuche

freakC++

Hallo zusammen,

ich stehe gerade auf dem Schlauch. Kann mir jemand sagen, warum hier false ausgegeben wird? 15 ist doch im Array? Warum funktioniert die Binärsuche nicht. Ich bin nicht auf die dunkle Seite gewechselt, obwohl A und n global sind.

#include <iostream>
using namespace std;

int A[] = {0,1,3,5,6,7,8,9,11,13,14,15};
int n = 12;

bool bin_search_rek(int x, int left, int right)
{
	int mitte = left + ((right - left) / 2);

	if(A[mitte] == x) 
		return true;
	else if (right < left)	
		return false;
	else
		if(A[mitte] < x)
			bin_search_rek(x, mitte+1, right);
		else
			bin_search_rek(x, left, mitte-1);

}
int main()
{
	cout << boolalpha << bin_search_rek(15,0,n-1);
	return 0;
}

Vielen Dank
lg, freakC++

Michael E.

Wer oder was hindert dich am Debuggen? Damit siehst du den Fehler sofort.

Edit: Ein vernünftiger Compiler warnt sogar bei dem Fehler.

freakC++

Anscheinend geben nicht alle Steuerelementpfade einen Wert zurück. Ich sehe ihn trotzdem nicht. Entweder wird "rechts" kleiner als "link" oder das Element wird gefunden. Welche Optionen soll es noch geben? Außerdem dürfte dann doch eigentlich die Rekursion nicht enden.

Danke dir!
lg, freakC++

Jockelx

Auch ein rekursiver Funktionsaufruf ist ein Funktionsaufruf.
Ersetz doch mal die unteren 'bin_search_rek'-Aufrufe durch 'ich_bin_nicht_rekursiv'.
Was passiert dann?

Liefern alle optionen einen Wert zurück?

freakC++

Jockelx schrieb:

Auch ein rekursiver Funktionsaufruf ist ein Funktionsaufruf.
Ersetz doch mal die unteren 'bin_search_rek'-Aufrufe durch 'ich_bin_nicht_rekursiv'.
Was passiert dann?

´

Dann kommt ein Fehler, weil es diese Funktion nicht gibt.

manni66 schrieb:

Liefern alle optionen einen Wert zurück?

Ja, eigentlich doch schon, weil es nur zwei Optionen gibt: Entweder wird das Element gefunden oder nicht. WEnn nicht, dann wird rechts kleiner als links.

Worauf wollt ihr hinaus? Welche Option übersehe ich denn? Mitte könnte 0 werden...mmmh...ne, das ist es nicht. Was übershee ich.....??

Danke

Jockelx

freakC++ schrieb:

Jockelx schrieb:

Auch ein rekursiver Funktionsaufruf ist ein Funktionsaufruf.
Ersetz doch mal die unteren 'bin_search_rek'-Aufrufe durch 'ich_bin_nicht_rekursiv'.
Was passiert dann?

´

Dann kommt ein Fehler, weil es diese Funktion nicht gibt.

Scherzkeks.
Das sollst du im Kopf machen -oder definiere dir die Funktion, die dann z.B. stumpf true zurückliefert.

Michael E.

Die Warnung lautet: "Nicht alle Steuerelementpfade geben einen Wert zurück."

Geh doch mal alle vier Pfade in deinem Funktionskörper durch und schaue, ob du in dem jeweiligen Pfad einen Wert zurückgibst.

freakC++

Jockelx schrieb:

Scherzkeks.
Das sollst du im Kopf machen -oder definiere dir die Funktion, die dann z.B. stumpf true zurückliefert.

Achso. Sorry. Ich hatte deinen Punkt nicht verstanden.

Ich schätze mal, es liegt einfach daran, dass ich kein "return" beim rekursiven Aufruf geschrieben habe. Toooollll. Ich dachte, dass es ein logischer Fehler wäre und habe sowas Banales gar nicht in Erwägung gezogen. Danke für die Hilfe.

lg, freakC++

freakC++

Fliegt eigentlich "mitte" beim rekursiven Aufruf vom Stack, also wird der Speicherplatz wieder freigegeben? Sonst wäre das nicht gerade schön, da sonst bei jedem Funktionsaufruf eine neue Variable angelegt wird.

lg, freakC++

Jockelx

Natürlich wird mitte bei jedem Aufruf angelegt und erst aufgeräumt, wenn die jeweilige Funktion fertig ist.
Ganz genauso wie bei anderen Funktionsaufrüfen auch.

SeppJ

freakC++ schrieb:

Fliegt eigentlich "mitte" beim rekursiven Aufruf vom Stack, also wird der Speicherplatz wieder freigegeben? Sonst wäre das nicht gerade schön, da sonst bei jedem Funktionsaufruf eine neue Variable angelegt wird.

Da du hier eine sogenannte Tailrekursion hast, ist es möglich, dass dies optimiert wird. Das ist aber schon eine der heftigeren Optimierungen, die bei den gängigen Compilern erst in den höheren Optimierungsstufen aktiviert werden. GCC und MSVC können das jedenfalls.

Wenn du dich drauf verlassen willst, dass alles optimal ist, dann musst du deinen Algorithmus von Hand zu einer Schleife umschreiben. Das ist auf jeden Fall möglich, das ist das was der Compiler bei der oben beschriebenen Optimierung tut.

Bashar

freakC++ schrieb:

Fliegt eigentlich "mitte" beim rekursiven Aufruf vom Stack, also wird der Speicherplatz wieder freigegeben? Sonst wäre das nicht gerade schön, da sonst bei jedem Funktionsaufruf eine neue Variable angelegt wird.

Das ist hier relativ egal, da die Rekursionstiefe sich logarithmisch zur Größe des Arrays verhält.

freakC++

SeppJ schrieb:

Wenn du dich drauf verlassen willst, dass alles optimal ist, dann musst du deinen Algorithmus von Hand zu einer Schleife umschreiben.

Also iterativ lösen?

SeppJ

freakC++ schrieb:

SeppJ schrieb:

Wenn du dich drauf verlassen willst, dass alles optimal ist, dann musst du deinen Algorithmus von Hand zu einer Schleife umschreiben.

Also iterativ lösen?

Wenn du sicher sein willst, dass es immer optimiert wird: Ja. Es gibt hier schließlich keinen zwingenden Grund zur Rekursion, außer, dass es hübscher aussieht. Beziehungsweise: Wenn du es iterativ löst, gibt es gar keinen Grund mehr zur Optimierung, weil das schon die Optimierung ist.