3. Binärsuche

Binärsuche

  • F

    Hallo zusammen,
    kann mir jemand sagen, warum ich hier keine Ausgabe bekomme. Das Konsolenfenster bleibt leer. Ich finde aber den Fehler nicht:

    #include <iostream>
using namespace std;

bool binsearch(int* arr, int n, int srch)
{
	bool succ = false;
	int start = 0;
	int end = n;
	int mid;

	while(!succ && start <= end)
	{
		mid = (start+end)/2;
		if(arr[mid]==srch)
			succ = true;
		else 
		{
			if(srch < arr[mid])
				end = mid-1;
			else
				end = mid+1;
		}
	}
	if(succ)
		return true;
	else
		return false;
}

int main()
{
	int arr[6]={1,2,3,4,5,6};

	cout << boolalpha << binsearch(arr,6,7) << endl; //es sollte false ausgegeben werden

}

    Vielen Dank
    lg,freakC++

    0
  • S

    Da sind so einige Fehler drin.
    - Du initialisierst end mit n, was bedeutet, dass end nicht mehr zur Sequenz gehört. Danach tust Du aber so, als wenn end das letzte Element der zu betrachtenden Sequenz ist.
    - Müsstest Du nicht auch in einem Fall start verändern?

    Dann kannst Du Dir noch succ sparen und einfach "return true;" statt "succ=true;" schreiben.

    Beim nächsten Mal bitte selbst mehr anstrengen!

    0
  • F

    Also, ich habe jetzt end = n-1 gesetzt, doch warum sollte ich "start" ändern. Hier ist ja nichts rekursiv. Das kleine Schönheitsproblem mit dem Rückgabewert habe ich geändert, doch das funktioniert noch nicht. Wenn ich ehrlich bin, habe ich versucht den Pseudocode von Wikipedia umzusetzen, doch bin ich irgendwie dran gescheitert.

    Daher brauche ich weitere Hilfe. Da das KOnsolenfenster nichts anzeigt, gehe ich davon aus, dass ich in einer Endlosschleife bin, doch das kann ich mir auch nicht erkären.

    Vielen Dank
    lg, freakC++

    0
  • N

    freakC++ schrieb:

    Daher brauche ich weitere Hilfe.

    freakC++, wie wärs, wenn du einmal den Debugger bemühen würdest? In letzter Zeit machst du wegen kleinsten Dingen einen Thread auf. Wir helfen zwar gerne, wenn um Verständnisfragen geht, aber es haben eben nicht alle Leute Lust, dir in deinem Programm Fehler zu suchen, weil du dich nicht selbst bemühst.

    0
  • S

    Du machst das ganze irgendwie komisch, o_O

    Ich würde es so machen:

    bool binSearch(int* array, int needle, int SIZE) {
  int mid = SIZE/2;
  if (array[mid] == needle) return true;
  int start = (array[mid]<needle?mid:0);
  for (int i = start; i < (start==0?mid:SIZE); i++) {
    if (array[i] == needle)
      return true;
  }
  return false;
}

    Ungetestet

    0
  • S

    Samyboy schrieb:

    Du machst das ganze irgendwie komisch, o_O
    Ich würde es so machen:

    Das sieht nicht weniger komisch aus. Lass den freak das doch mal selbst machen.

    0
  • F

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

    0
  • F

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

    0
  • F

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

    0
  • N

    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);
    0
  • F

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

    0
  • N

    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.

    0
  • F

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

    0
  • N

    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?

    0
  • ?

    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]

    0
  • F

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

    0
  • V

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

    0
  • ?
     

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

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

    0
  • F

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

    0
  • N

    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.

    0
Anmelden zum Antworten