//--------------------------------------------------
//CPPfile: binaeresuche.cpp
//Beschreibung: Binäre Suche auf einem Array
//Autor: Tobias Schwalb & Michael Tansella, ITIV
//Erstellt: 13.07.2011
//Version: 1.0
//--------------------------------------------------
#include
#include
using namespace std;
//Zwei unterschiedliche Implementierungen zur binären Suche
int binaereSuche( long werte[], int laenge, long gesuchterWert );
int binaereSucheRekursiv( long werte[], int anfang, int ende, long gesuchterWert );
//Ein kleines Testprogramm zum Anlegen eines sortierten Arrays und
//abfragen des gesuchten Wertes von der Tastatur, dieser wird im Array
//mit Hilfe der binären Suche gesucht und die entsprechende Position
//ausgeben, wenn der Werte im Array vorhanden ist, ansonsten wird eine
//Fehlermeldung ausgegeben
int main() {
//long werte[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
long werte[10] = {4, 9, 34, 43, 45, 66, 88, 111, 324, 345};
long gesuchterWert;
cout << "Bitte den gesuchten Wert eingeben: ";
cin >> gesuchterWert;
int position = binaereSuche( werte, 10-1, gesuchterWert );
//int position = binaereSucheRekursiv( werte, 0, 10-1, gesuchterWert );
if( position == -1 ) {
cout << endl << "Der gesuchte Wert " << gesuchterWert << " wurde nicht im Array gefunden" << endl;
} else {
cout << endl << "Der gesuchte Wert " << gesuchterWert << " befindet sich an Position: " << position + 1 << endl;
}
system( "pause" );
return 0;
}
//Implementierung der binären Suche
//entsprechend dem Pseudocode auf Wikipedia (Suchwort: Binäre Suche)
int binaereSuche( long werte[], int laenge, long gesuchterWert ) {
bool erfolgreich = false;
int anfang = 0;
int mitte;
while( erfolgreich == false && anfang <= laenge ) {
mitte = (anfang + laenge) / 2;
if( werte[mitte] == gesuchterWert ) {
erfolgreich = true;
} else {
if( gesuchterWert < werte[mitte] ) {
laenge = mitte - 1;
} else {
anfang = mitte + 1;
}
}
}
if( erfolgreich == true ) {
return mitte;
} else {
return -1;
}
}
//Implementierung der binären Suche
//entsprechend dem Pseudocode der Vorlesung 10 - ab Folie 10-9
int binaereSucheRekursiv( long werte[], int anfang, int ende, long gesuchterWert ) {
int mitte = ( anfang + ende ) / 2;
if( werte[mitte] == gesuchterWert ) {
return mitte;
} else {
if( ( ende - anfang ) > 0 ) {
if( werte[mitte] < gesuchterWert ) {
return binaereSucheRekursiv( werte, mitte + 1, ende, gesuchterWert );
} else {
return binaereSucheRekursiv( werte, anfang, mitte, gesuchterWert );
}
} else {
return -1;
}
}
}