C++ Binäre Suche (Fehlersuche) C++

[Herbert1]

Halle zusammen, kann mir bitte jemand sagen, warum folgender C++ Code nicht funktioniert? Es gibt keine Fehlermeldung, allerdings kommt nie das korrekte Ergebnis heraus :/

Ich möchte ein sortiertes Array (aiZahlen) mithilfe der binären Suche nach einer Zahl (iGesucht durchsuchen). Anschließend soll ausgegeben werden, ob die Zahl enthalten ist oder nicht.

#include <iostream>
using namespace std;

int main()
{
	int iIndex = 10;
	int aiZahlen[] = { 1,2,3,4,5,6,7,8,9,10 };

	int iMitte=0, iLinks = 0, iRechts = 1;
	char cGefunden = 'n';
	int iGesucht = 5;
	iLinks = aiZahlen[0];
	iRechts = aiZahlen[9];

	while (cGefunden == 'n' && iLinks < iRechts)
	{
		cout << "Mitte =" << iMitte << "    " << aiZahlen[iMitte] << endl;
		iMitte = (iLinks + iRechts) / 2;

		if (aiZahlen[iMitte] == iGesucht)
		{
			cGefunden = 'j';
		} //if
		else
		{
			if (iGesucht>aiZahlen[iMitte])
			{
				iLinks = iMitte + 1;
			} //else-if
			else
			{
				iRechts = iMitte - 1;
			} //else-if-else
		} //else
	} //while Klammer

	if (cGefunden == 'j')
	{
		cout << "Gefunden";
	}
	else {
		cout << "Nicht gefunden";
	}


	cin.get(); cin.get();
	return 0;
}

Ich bitte um Antworten

 

[convexus]

Was spricht gegen die Verwendung der Standard-Bibliothek?

 

[pipip]

if (aiZahlen[iMitte] == iGesucht)
{
cGefunden = 'j';
}

sobald die Zahl gefunden ist, wird ja cGefunden auf das Char "j" gesetzt.

In der While Schleife hast du ja die Bedienung cGefunden == 'n', sollte da nicht ein "j" sein ? Sonst geht er ja trotz dem Finden nicht aus der while schleife oder ?

Sprich:

while (cGefunden == 'n' && iLinks < iRechts)

die erste Abbruchbedingung ist immer richtig und sobald iLinks < iRechs ist, wird die schleife abgebrochen und du bekommst das falsche ergebnis.

Also wenn dann bricht das Teil schon früher ab, oder es kommt in eine endlosschleife, kann das sein ?

convexus
Übung nehme ich an, aber nach der Aufgabenstellung, wäre die Zahlenreihe eh ein Feld und ich würde nur jeden Eintrag des Feldes mit 5 abbfragen und bei /n beim nicht finden einfach abbrechen.
Wäre aber halt C.

 

[MajorApplePie]

links rechts mitte
1 10 5
1 4 2
3 4 3
4 4 break da links nicht < rechts

 

[S.Kara]

Müssten iLinks und iRechts nicht auch so aussehen?

iLinks = 0;
iRechts = 9;

Im Kopf der While reicht auch "iLinks <= iRechts", dafür z.B. hinter "cGefunden = 'j';" dann noch ein "break;".

iMitte wird auch erst ausgegeben und dann berechnet, evtl. sollte man das vielleicht umdrehen.

 

[WingX]

Ganz wichtig bei solchen Sachen: nicht Inhalte und Indizes durcheinander werden.
iLinks und iRechts sind die Inhalte des Arrays, iMitte wird als Mittelwert davon bestimmt.
Dann wird jedoch per aiZahlen[iMitte] der Mittelwert der Inhalte als Index für ein Feld verwendet.
Das kann böse ins Auge gehen.

 

[convexus]

@pipip: Ich halte die Anwendung der Standard-Bbliothek für eine sehr gute Übung für C++. Ist auch nicht trivial und erfordert das Verständnis der verwendeten Abstraktionen hier z.B. Iterator-Konzept und wie dieses auf das Array angewendet werden kann. Tatsächlich ist C++ ohne die STL nur die Hälfte.