Binary suche |
Pommes unregistriert
|
|
Meine Frage:
Wie kann hier dafür sorgen, dass alle Treffer einer Zahl angezeigt wird?
ist es nicht binarysearch?
Ich danke euch für eure Hilfe
Meine Ideen:
/*#################################
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;
}
|
|
18.07.2016 21:55 |
|
|
|
Du kennst den Index einer Übereinstimmung. Von da aus kannst du linear (oder auch binär) nach oben und unten gehen, und suchen, wo es keine Übereinstimmung mehr gibt.
__________________ Syntax Highlighting fürs Board (Link)
|
|
19.07.2016 08:42 |
|
|
|