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