Binäre Suche - Verständnisfrage



  • Hallo zusammen.

    In meinem Lehrheft ist gerade die binäre Suche ein Thema. Dazu habe ich im Netz ein wenig gestöbert und habe dann auch hier im Forum etwas dazu gefunden.
    Mein Code sieht erstmal im gesamten so aus:

    /*#################################
    Binäre Suche
    #################################*/
    
    #include <iostream>
    #include <time.h>
    #include <stdlib.h>
    
    using namespace std;
    
    int main()
    {
        // die maximale Anzahl der Werte
        const int MAX = 100;
        // ei 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 unsortierten Werte sind: " << endl << endl;
        for (int index = 0; index < MAX; index++)
            cout << werte[index] << ' ';
        cout << endl << 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++)
                if (werte[k] > werte[k + 1]) {
                    tauschTemp = werte[k];
                    werte[k] = werte[k + 1];
                    werte[k + 1] = tauschTemp;
                }
        // die sortierte Ausgabe
        cout << endl;
        cout << "Die sortierten Werte sind: " << endl << endl;
        for (int index = 0; index < MAX; index++)
            cout << werte[index] << ' ';
        cout << endl << 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 Zahl kleiner als die Zahl in der Mitte, dann wird links weiter gesucht
            if (kriterium < werte[mitte])
                ende = mitte -1;
            // sonst wird rechts weiter gesucht bzw wir haben die Zahl gefunden
            else
                if (kriterium > werte[mitte])
                    anfang = mitte + 1;
                else
                    gefunden = true;
        }
    
        for (int i = mitte; i < MAX && werte[i] == kriterium; i++ )
            cout << "Der Wert " << kriterium << " befindet sich an der Position " << i + 1 << endl;
    
        if (gefunden == false)
            cout << "Der Wert " << kriterium << " wurde nicht gefunden. " << endl;
    
        return 0;
    }
    

    Speziell geht es mir um den letzten Teil den ich hier im Forum gefunden habe.

    for (int i = mitte; i < MAX && werte[i] == kriterium; i++ )
            cout << "Der Wert " << kriterium << " befindet sich an der Position " << i + 1 << endl;
    
        if (gefunden == false)
            cout << "Der Wert " << kriterium << " wurde nicht gefunden. " << endl;
    
        return 0;
    

    Er bewirkt ja, dass alle Treffer die zum Suchkriterium passen ausgegeben werden.
    Mein Frage nun, wie das ganze? Es wird doch nur immer wieder die Suche ausgeführt, bis die Liste durch ist und alles was er findet zeigt er an oder?



  • Wo wird da eine Suche ausgeführt?
    Wenn du "gefundene" Programme nicht verstehst, benutze einen Debugger und beobachte was sie tun.

    Warum musst du überhaupt einen alten Thread mit C mit cout aus dem Grab holen? In C++ benutzt man std::binary_search.



  • Dieses "gefundene" Programm steht bis auf den besagten letzten Teil in meinem Heft.

    Eigentlich wollte ich auch nur wissen ob ich es richtig verstanden habe, denn im Gegensatz zu manch anderen bin ich nicht mit der Fähigkeit geboren worden C++ sofort zu beherrschen. Ich bin gerade dabei es zu lernen und wollte nur etwas Hilfestellung.

    Trotzdem danke für den Tipp



  • DerGerd schrieb:

    Dieses "gefundene" Programm steht bis auf den besagten letzten Teil in meinem Heft.

    Was für ein Zufall, dass er identisch mit dem Code aus dem Thread von 2012 ist ...



  • Ja, weil der Code aus einem Studienheft stammt!
    Erst richtig lesen und dann Unterstellungen verbreiten!



  • Ok, hat sich erledigt. Alles geklärt


Log in to reply