bineare Suche Problem

[Jos]

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;
}

[DirkB]

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.

[Werner Salomon]

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

[Gast]

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