Vorlesung Informatik 2 - Teil B: Theorie
1.3 Binäre Suche
Hier zunächst einige Beispiele für
Komplexitäten:
for(int i=0;i<n;i++) { ... } - O(N)
for(int i=0;i<n;i++) {
for(int j=0;j<n;j++) { ... } - O(N2)
}
for(int i=0;i<n;i++) {
for(int j=0;j<i;j++) { ... } - O(N2) die Innere Schleife läuft im Mittel bis N/2
}
Wir haben gesehen, dass die lineare Suche in einem Datenbestand die
Komplexität O(N) hat.
Suche ist ein extrem häufige Aufgabe von Computern, jeder Klick im Internet löst wahrscheinlich eine Suche aus. Deshalb stellt sich die Frage, ob man die Komplexität einer Suche verbessern kann.
Die Antwort: wenn der Datenbestand sortiert ist, kann man ein wesentlich schnelleres Verfahren anwenden: die binäre Suche.
Beispiel. Ein Telefonbuch, das nicht sortiert wäre, wäre nutzlos.
Stellen wir uns folgendes Spiel vor: ein Teilnehmer denkt sich eine Zahl zwischen 1 und 100, die anderen sollen mit möglichst wenig ja/nein Fragen die Zahl herausfinden.
Man findet schnell die Strategie, zu fragen, ob die Zahl zwischen 1 und 50 liegt, bei der Antwort nein lautet die nächste Frage ob die Zahl zwischen 1 und 25 liegt u.s.w. Spätestens nach 7 Fragen haben wir die Zahl gefunden, eine lineare Suche würde im Mittel 50 Fragen brauchen.
In einem Java-Pseudocode würde dieser Algorithmus etwa so aussehen:
int start=1, ende=100;
while(start<ende){'
int mitte=(start+ende)/2;
if(frage("Ist die Zahl großer als " +mitte)) start=mitte+1;
else ende=mitte;
}
melde("Die gesuchte Zahl ist " + start);
Dieser Algorithmus verringert die Datenmenge, in der noch gesucht werden muss, in jedem Schritt um die Hälfte, am Anfang ist n=100, dann 50, dann 25 us.w.
Das führt zu einer logarithmischen Komplexität O(log N).