Binäre Suche gibt nur einen Treffer aus - auch wenn der Wert mehrmals vorkommt

[freewibes]

Hallo zusammen,

ich bräuchte mal wieder Hilfe. Die Rekursion funktioniert nur bei der linearen Suche - bei der binären wird immer nur ein Treffer ausgegeben.

Anbei der Code. Ich möchte den Code nicht gänzlich umschreiben oder in Vektoren suchen - Ziel ist es lediglich die Suche nach dem Treffer wieder aufzurufen.

Bei der linearen Suche hat es mit folgendem Code funktioniert:
{
if (werte[suchen] == mitte)

if (gefunden = true);
cout << "Der Wert " << kriterium << " befindet sich an der Position " << mitte + 1 << endl;

suchen++;

Ich habe versucht diese Lösung auf die binäre Suche zu übertragen - funktioniert aber nicht. Kann mir jemand helfen?

Schon mal vielen Dank.

/*##############################################
Binäre Suche
##############################################*/
#include <iostream>

using namespace std;
int suchen = 0;

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 = i + 1 ; k < MAX; k++)
            //wenn ein Folgeelement größer ist als das aktuelle Element, wird getauscht
            if (werte[i] > werte[k]) {
                //den Wert sichern, damit er nicht überschrieben wird
                tauschTemp = werte[k];
                werte[k] = werte[i];
                werte[i] = 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;

    }
cout<< "Die Werte bis zur Mitte sind: " <<endl;
for (int index = 0; index < mitte; index++)
        cout << werte[index] << ' '<<endl;

{
        if (werte[suchen] == mitte)

            if (gefunden = true);
        cout << "Der Wert " << kriterium << " befindet sich an der Position " << mitte + 1 << endl;

        suchen++;
    }

    if (gefunden ==false)
        cout << "Der Wert " << kriterium << " wurde nicht gefunden. " << endl;

    return 0;
}

[Skym0sh0]

was du da vorhast(sofern ich dich richtig verstehe) ist etwas naja schräg. mit einer binären suche mehrere gleiche elemente zu finden ist schon etwas doof.

auf der anderen seite ist ja eine der vorbedingungen, dass deine liste sortiert ist. und dann kannst du einfach zählen wie viele elemente gleich sind, wenn du deine nachbarn des gefundenen elements anguckst.

int count = 0;
// ...

// blabla suche usw.
if( gefunden )
{
    int index = mitte-1;
    while ( index != 0 && werte[index] == werte[mitte] ) 
    {
        count++;
        index--;
    }
    index = mitte+1;
    while ( index != MAX && werte[index] == werte[mitte] ) 
    {
        count++;
        index++;
    }
}

//ungetestet

so in etwa stelle ich mir das vor.
aber deine binäre suche in einer schleife laufen zu lassen würde ich dir nicht raten.

hat dein lehrbuch eigentlich schon funktionen behandelt?

[Werner Salomon]

Hallo freewibes,

freewibes schrieb:

Ich habe versucht diese Lösung auf die binäre Suche zu übertragen - funktioniert aber nicht. Kann mir jemand helfen?

Der Trick besteht darin, nicht mit der Suche aufzuhören, wenn Du ein ' kriterium ' gefunden hast. Im Prinzip suchst Du ja nicht 'kriterium', sondern den Übergang von 'kein kriterium' zu 'kriterium'.

Dazu ersetze einfach die Zeilen 64 bis 80 durch

//und jetzt suchen
    //dabei wird immer wieder in links und rechts geteilt
    // Bem.: ende2 zeigt zunächst hinter(!) das letzte Element
    for( int ende2 = MAX; anfang != ende2; )
    {
        mitte = (anfang + ende2) / 2;
        if( werte[mitte] < kriterium )
            anfang = mitte + 1;
        else
            ende2 = mitte; // evt. steht ende2 auch auf dem gefundenen Wert!
    }
    gefunden = (anfang != MAX) && (werte[anfang] == kriterium);
    mitte = anfang; // Bem.: wird später noch benötigt (s.u.)

Im C++-Standard gibt es genau diesen Algorithmus - er heißt dort lower_bound.

Falls gefunden==true ist, steht in 'mitte' jetzt der erste Index ab dem wert[mitte]==kriterium true ist. Wenn Du jetzt die weiteren Elemente mit dem Wert ' kriterium ' suchst, so ist es natürlich Overkill, dafür wieder eine binäre Suche zu starten, denn die stehen nun alle hinter wert[mitte] , solange ' kriterium ' nicht mehr erfüllt ist, oder das Ende erreicht ist.

Btw.: deklariere Deine Variablen erst dann, wenn Du sie auch benötigst. Und versuche Dein Programm in einzelne Funktionen zu teilen. Beides schafft Überblick.

Gruß
Werner

[freewibes]

Hallo Werner,

erst mal vielen Dank für die Hilfe - habe Deinen Code eingesetzt. Leider gibt es immer noch nur eine Aussgabe - habe ich einen Fehler gemacht?

/*##############################################
Binäre Suche
##############################################*/
#include <iostream>

using namespace std;
int suchen = 0;

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 = i + 1 ; k < MAX; k++)
            //wenn ein Folgeelement größer ist als das aktuelle Element, wird getauscht
            if (werte[i] > werte[k]) {
                //den Wert sichern, damit er nicht überschrieben wird
                tauschTemp = werte[k];
                werte[k] = werte[i];
                werte[i] = 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
    // Bem.: ende2 zeigt zunächst hinter(!) das letzte Element
    for( int ende2 = MAX; anfang != ende2; )
    {
        mitte = (anfang + ende2) / 2;
        if( werte[mitte] < kriterium )
            anfang = mitte + 1;
        else
            ende2 = mitte; // evt. steht ende2 auch auf dem gefundenen Wert!
    }
    gefunden = (anfang != MAX) && (werte[anfang] == kriterium);
    mitte = anfang; // Bem.: wird später noch benötigt s.u.

cout<< "Die Werte bis zur Mitte sind: " <<endl;
for (int index = 0; index < mitte; index++)
        cout << werte[index] << ' '<<endl;

{
        if (werte[suchen] == mitte)

            if (gefunden = true);
        cout << "Der Wert " << kriterium << " befindet sich an der Position " << mitte + 1 << endl;

        suchen++;
    }

    if (gefunden ==false)
        cout << "Der Wert " << kriterium << " wurde nicht gefunden. " << endl;

    return 0;
}

[freewibes]

Skym0sh0 schrieb:

was du da vorhast(sofern ich dich richtig verstehe) ist etwas naja schräg. mit einer binären suche mehrere gleiche elemente zu finden ist schon etwas doof.

auf der anderen seite ist ja eine der vorbedingungen, dass deine liste sortiert ist. und dann kannst du einfach zählen wie viele elemente gleich sind, wenn du deine nachbarn des gefundenen elements anguckst.

int count = 0;
// ...

// blabla suche usw.
if( gefunden )
{
    int index = mitte-1;
    while ( index != 0 && werte[index] == werte[mitte] ) 
    {
        count++;
        index--;
    }
    index = mitte+1;
    while ( index != MAX && werte[index] == werte[mitte] ) 
    {
        count++;
        index++;
    }
}

//ungetestet

so in etwa stelle ich mir das vor.
aber deine binäre suche in einer schleife laufen zu lassen würde ich dir nicht raten.

hat dein lehrbuch eigentlich schon funktionen behandelt?

Hey, vielen Dank für die Hilfe. Leider klappt es nicht so ganz - habe den Code zwar eingefügt - kriege den Code aber nicht zum Laufen.

Funktionen haben wir immer nur "wenn es der Aufgabe nicht schadet". Momentan sollen eher Codes umgeschrieben bzw. die Schönheitsfehler ausgemerzt werden.

Vielleicht kannst du dir den Code noch mal anschauen?

/*##############################################
Binäre Suche
##############################################*/
#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 = i + 1 ; k < MAX; k++)
            //wenn ein Folgeelement größer ist als das aktuelle Element, wird getauscht
            if (werte[i] > werte[k]) {
                //den Wert sichern, damit er nicht überschrieben wird
                tauschTemp = werte[k];
                werte[k] = werte[i];
                werte[i] = 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;
    }

   int count = 0;
// ...

// blabla suche usw.
if( gefunden )
{
    int index = mitte-1;
    while ( index != 0 && werte[index] == werte[mitte] )
    {
        count++;
        index--;
    }
    index = mitte+1;
    while ( index != MAX && werte[index] == werte[mitte] )
    {
        count++;
        index++;
    }
    return 0;
}

[Werner Salomon]

Hallo freewibes,

freewibes schrieb:

erst mal vielen Dank für die Hilfe - habe Deinen Code eingesetzt. Leider gibt es immer noch nur eine Ausgabe - habe ich einen Fehler gemacht?

.. na ja - Du hast es gar nicht codiert. Wo in Deinem Code erwartest Du denn eine Ausgabe aller gefundenen Elemente?

Der Code zwischen den Zeile 85 bis 93 scheint eher so ein Resteposten aus ehemaligen Programmsegmenten zu sein. Sinn macht er keinen.

Werner Salomon schrieb:

Falls gefunden==true ist, steht in 'mitte' jetzt der erste Index ab dem wert[mitte]==kriterium true ist. Wenn Du jetzt die weiteren Elemente mit dem Wert ' kriterium ' suchst, ... die stehen nun alle hinter wert[mitte] , solange ' kriterium ' nicht mehr erfüllt ist, oder das Ende erreicht ist.

Und genau die Elemente kannst Du jetzt ausgeben. Wobei ich nicht sicher bin, ob es das ist, was Du willst. Also hinter der Ausgabe aller Elemente bis 'mitte' - also ab Zeile 83 ersetze Deinen Code durch folgendes:

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;

Werner Salomon schrieb:

Btw.: deklariere Deine Variablen erst dann, wenn Du sie auch benötigst. Und versuche Dein Programm in einzelne Funktionen zu teilen. Beides schafft Überblick.

Und beherzige meinen Rat - dann wärst Du vielleicht schon selbst drauf gekommen.

Gruß
Werner

[freewibes]

Hallo Werner,

vielen Dank - so funktioniert es. Vielen Dank auch für die Tipps.

[DerGerd]

Hallo,

auch wenn das hier schon ziemlich alt ist, kann mir vielleicht trotzdem jemand sagen was der letzt Code bewirkt?
Eigentlich doch nur das die Suche nach einem Ergebnis weiter läuft bis das Ende der Liste erreicht ist oder? Und halt jeder Treffer ausgegeben wird.

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;

[DerGerd]

Keiner der mir kurz helfen könnte?