bineare Suche Problem



  • Hallo zusammen,

    ich habe folgendes Problem:

    Mein Programm zur binären Suche liefert immer nur einen Treffer, auch wenn sich die Zahl mehrfach in der Liste befindet.

    Wie kann ich nun dafür sorgen, dass alle Treffer einer Zahl angezeigt werden?
    Hat jemand eine Idee?

    hier der code:

    #include <iostream>
    
    using namespace std;
    
    int main()
    {
        //die maximale Anzahl der Werte
        const int MAX = 100;
        //ein Feld für die Werte
        int werte[MAX];
        //wurde schon ein Wert gefunden?
        bool gefunden = false;
        //für die Suche
        int kriterium = 0;
        int ende = MAX - 1, anfang = 0, mitte;
        //eine Hilfsvariable für den Tausch
        int tauschTemp;
    
        //den Zufallsgenerator initialisieren
        srand(time(NULL));
    
        cout << "Binaere Suche" << endl;
        //die Werte setzen, benutzt werden zufällige Zahlen bis 200
        for (int index = 0; index < MAX; index++) {
            werte[index] = rand() % 200;
        }
    
        //zur Kontrolle unsortiert ausgeben
        cout << "Die unsortieren Werte sind: " << endl;
        for (int index = 0; index < MAX; index++)
            cout << werte[index] << ' ';
    
        cout << endl;
        cout << "Jetzt wird ueber Bubblesort sortiert.." << endl;
    
        //Sortieren
        //alle Werte durchgehen und dann von vorne nach hinten vergleichen
        for (int i = 0; i < MAX; i++)
            for (int k = 0 ; k < MAX - i - 1; k++)
                //wenn das aktuelle Element größer ist das Folgeelement, wird getauscht
                if (werte[k] > werte[k + 1]) {
                    //den Wert sichern, damit er nicht überschrieben wird
                    tauschTemp = werte[k];
                    werte[k] = werte[k + 1];
                    werte[k + 1] = tauschTemp;
                }
    
        //die sortierte Ausgabe
        cout << endl;
        cout << "Die sortierten Werte sind: " << endl;
        for (int index = 0; index < MAX; index++)
            cout << werte[index] << ' ';
    
        cout << endl;
        //Abfrage des Suchkriteriums
        cout << "Wonach soll gesucht werden? ";
        cin >> kriterium;
    
        //und jetzt suchen
        //dabei wird immer wieder in links und rechts geteilt
        while ((ende >= anfang) && (gefunden == false)) {
            //die Mitte berechnen
            mitte = (anfang + ende) / 2;
            //ist die die Zahl kleiner als die Zahl in der Mitte, dann wird links weitergesucht
            if (kriterium < werte[mitte])
                ende = mitte - 1;
            //sonst wird rechts weitergesucht bzw. wir haben die Zahl gefunden
            else
                if (kriterium > werte[mitte])
                    anfang = mitte + 1;
                else
                    gefunden = true;
        }
    
        if (gefunden == true)
            cout << "Der Wert " << kriterium << " befindet sich an der Position " << mitte + 1 << endl;
        else
            cout << "Der Wert " << kriterium << " wurde nicht gefunden. " << endl;
    
        return 0;
    }
    


  • Mal auf das wesentliche reduziert

    while ((ende >= anfang) && (gefunden == false)) {
    ...
                else
                    gefunden = true;
    }
    Ausgabe
    

    Es ist nicht weiter verwunderlich, dass du nur einen Wert bekommst. Du brichst die Suchschleife ja nach dem ersten Fund ab.



  • Hallo Jos,

    das eigentliche Problem besteht darin, dass Du nach irgendeinem Wert suchst, der gleich dem Kriterium ist. Auch wenn mehr als ein passender Wert in dem Array vorkommen. Du musst zunächst nach dem ersten(!) vorkommenden Kriterium suchen. Das bedeutet auch, das der Wert wert[anfang] während der Suche kleiner (nicht gleich!) dem Kriterium sein muss. So fällt der gesuchte Wert immer in das Intervall [anfang,ende] .
    Es ist leichter zu programmieren, wenn ' ende ' immer hinter(!) den letzten Wert zeigt.

    Ich habe Dir Deinen Code mal umgestellt:

    #include <iostream>
    #include <ctime>
    #include <cstdlib>
    #include <algorithm>
    
    using namespace std;
    
    int main()
    {
        //die maximale Anzahl der Werte
        const int MAX = 100;
        //ein Feld für die Werte
        int werte[MAX];
    
        //den Zufallsgenerator initialisieren
        srand(time(NULL));
    
        cout << "Binaere Suche" << endl;
        //die Werte setzen, benutzt werden zufällige Zahlen bis 200
        for (int index = 0; index < MAX; index++) {
            werte[index] = rand() % 200;
        }
    
        //zur Kontrolle unsortiert ausgeben
        cout << "Die unsortieren Werte sind: " << endl;
        for (int index = 0; index < MAX; index++)
            cout << werte[index] << ' ';
    
        cout << endl;
        cout << "Jetzt wird ueber Bubblesort sortiert.." << endl;
    
        //Sortieren
        //alle Werte durchgehen und dann von vorne nach hinten vergleichen
        for (int i = 0; i < MAX; i++)
            for (int k = 0 ; k < MAX - i - 1; k++)
                //wenn das aktuelle Element größer ist das Folgeelement, wird getauscht
                if (werte[k] > werte[k + 1]) {
                    //den Wert sichern, damit er nicht überschrieben wird
                    int tauschTemp = werte[k];
                    werte[k] = werte[k + 1];
                    werte[k + 1] = tauschTemp;
                }
    
        //die sortierte Ausgabe
        cout << endl;
        cout << "Die sortierten Werte sind: " << endl;
        for (int index = 0; index < MAX; index++)
            cout << werte[index] << ' ';
    
        cout << endl;
        //Abfrage des Suchkriteriums
        cout << "Wonach soll gesucht werden? ";
        //für die Suche
        int kriterium = 0;
        cin >> kriterium;
    
        //und jetzt suchen
        //dabei wird immer wieder in links und rechts geteilt
        int anfang = 0;
        for( int ende = MAX; ende > anfang; ) {
            //die Mitte berechnen
            int mitte = (anfang + ende) / 2;
            //ist die Zahl in der Mitte kleiner als die gesuchte Zahl, dann wird rechts weitergesucht
            if (werte[mitte] < kriterium )
                anfang = mitte + 1;
            else //sonst wird links weitergesucht
                ende = mitte;
        }
        int upper = anfang;
        for( ; !(kriterium < werte[upper]); ++upper ) // jetzt noch die obere Grenze suchen
            ;
        if( werte[anfang] == kriterium ) // oder: if( anfang != upper ) // Bem.: Intervall nicht leer
            cout << "Der Wert " << kriterium << " befindet sich im (halboffenen) Intervall [" << anfang << "; " << upper << ")"<< endl;
        else
            cout << "Der Wert " << kriterium << " wurde nicht gefunden. " << endl;
    
        return 0;
    }
    

    Tipp: deklariere die Variablen erst dann, wenn Du sie benötigst.

    Bem.: auch im Fall von 'nicht gefunden' zeigt ' anfang ' auf die 'beste passende' Stelle im Array.

    Gruß
    Werner



  • Kleiner Tipp. Benutze

    mitte = anfang + (ende - anfang) / 2;
    // statt
    mitte = (anfang + ende) / 2;
    

    um einen Overflow für große Array zu vermeiden. Siehe dazu: http://en.wikipedia.org/wiki/Binary_search_algorithm#Implementation_issues


Log in to reply