Mathe-Beispiel
Die binäre Suche
... ist ein Suchverfahren für Zahlen, die ihrer Größe nach sortiert sind.
Also zum Beispiel wenn wir die 8 suchen (X steht für eine beliebige Zahl):
X X X X X X X X X X
Man könnte nach der herkömmlichen, sequentiellen Methode arbeiten und alle Zahlen der Reihe nach ansehen, wenn man Pech hat braucht man dafür aber - in diesem Fall - 10 Schritte.
Die binäre Suche dagegen ist viel effektiver:
Man sieht sich die Zahl (hier ungefähr) in der Mitte an:
X X X X 5 X X X X X
5<8 also ist die 8 in der 2. Hälfte zu finden.
Man sieht also wieder in der Mitte der übriggebliebenen Hälfte:
X X 8 X X -> Zahl gefunden
Mit jedem Schritt wird also die Zahlenmenge halbiert.
Anzahl der Zahlen | Sequentielle Suche | Binäre Suche |
|---|---|---|
1 | 1 | 1 |
2 | 2 | 2 |
4 | 4 | 3 |
8 | 8 | 4 |
16 | 16 | 5 |
32 | 32 | 6 |
64 | 64 | 7 |
Ausgehend von der Tabelle ergibt sich für die Anzahl der Arbeitsschritte x bei der binären Suche die folgende Formel. n ist die Anzahl der Zahlen. 
|
Man erkennt am folgenden Graphen die Effektivität der Binären Suche (rot) gegenüber der Sequentiellen (schwarz).
|
