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