Laufzeit der Binärsuche

Wir wissen, dass wir bei einer linearen Suche bei einem Array von $n$‍ Elementen genau $n$‍ Mal raten müssen. Du weißt wahrscheinlich schon intuitiv, dass bei der binären Suche weniger oft geraten werden muss als bei der linearen Suche. Du hast wahrscheinlich auch bemerkt, dass der Unterschied zwischen der maximal benötigten Anzahl an Malen, die man bei der linearen Suche und bei der binären Suche raten muss, immer frappierender wird, je länger das Array wird. Schauen wir mal, wie wir diese maximale Anzahl bei der binären Suche analysieren können.

Die Schlüsselidee ist dass wenn bei der binären Suche falsch geraten wird der Teil des Arrays, der die weiterhin möglichen Werte enthält, mindestens um die Hälfte reduziert wird. Wenn dieser Teil 32 Elemente hat, wird, wenn falsch geraten wird, höchstens so viel abgezogen, dass noch maximal 16 übrig bleiben. Die binäre Suche halbiert den Teil mit den möglichen Werten jedes Mal, wenn falsch geraten wird.

Wenn wir mit einem Array der Länge 8 beginnen, wird der Teil mit den möglichen Werten erst auf 4 reduziert, dann auf 2, dann auf 1. Wenn dieser Teil nur noch ein Element enthält, kann nicht weiter geraten werden, weil dann die geratene Zahl für den Teil mit einem Element entweder wahr oder falsch ist. Damit sind wir fertig. Bei einem Array mit der Länge 8 muss bei der binären Suche also mindestens 4 Mal geraten werden.

Was denkst du würde bei einem Array von 16 Elementen passieren? Wenn du sagen würdest, dass mit dem ersten Mal raten mindestens 8 Elemente eliminiert würden, so dass höchstens 8 übrigbleiben, hast du das System verstanden. Also müssen wir bei 16 Elementen höchstens fünf Mal raten.

Inzwischen erkennst du wahrscheinlich das Muster. Jedes Mal, wenn wir die Größe des Arrays verdoppeln, müssen wir mindestens ein Mal öfter raten. Nehmen wir nun an, wir müssen höchstens $m$‍ Mal raten für ein Array der Länge $n$‍. Dann würde man bei einem Array der Länge $2n$‍ durch das erste Mal raten den Teil des Arrays mit den möglichen Werten auf die Größe $n$‍ reduzieren, und höchstens $m$‍ Mal raten übrig lassen, was insgesamt höchstens $m+1$‍ Mal raten entspricht.

Betrachten wir den allgemeinen Fall eines Arrays der Länge $n$‍. Wir können die Anzahl der Male, die wir im schlimmsten Fall raten müssen, als die Anzahl der Male ausdrücken, die wir den Bereich immer wieder halbieren können - angefangen bei $n$‍ - bis wir den Wert 1 erhalten, plus 1 dazu. Aber das ist schwer auszuschreiben.

Zum Glück gibt es eine mathematische Funktion, die genau das Gleiche aussagt wie die Anzahl der Male die wir, angefangen bei $n$‍, immer wieder halbieren müssen, bis wir zum Wert 1 kommen: der Logarithmus von $n$‍ zur Basis 2. Wir schreiben ihn als ${\log }_{2}n$‍, aber in der Informatik wird er manchmal auch als $\lg n$‍ geschrieben. (Willst du Logarithmen wiederholen? Hier findest du mehr dazu.)

Hier ist eine Tabelle, welche die Logarithmen zur Basis 2 von verschiedenen Werten von $n$‍ zeigt:

Wir können diese Tabelle auch als Diagramm darstellen:

Wenn wir auf kleinere Werte von n hineinzoomen:

Die Logarithmusfunktion wächst sehr langsam. Logarithmen sind das Gegenteil von Exponentialfunktionen, die sehr langsam wachsen, so dass wenn ${\log }_{2}n=x$‍, dann $n=2^x$‍. Zum Beispiel, weil ${\log }_{2}128=7$‍, wissen wir, dass $2^7=128$‍.

Das macht es einfach, die Laufzeit eines binären Suchalgorithmus für ein $n$‍, das genau eine Potenz von 2 ist, zu berechnen. Wenn $n$‍ 128 ist, benötigt die binäre Suche höchstens 8 (${\log }_{2}128+1$‍) Versuche.

Was ist, wenn $n$‍ keine Potenz von 2 ist? In diesem Fall können wir uns die nächstkleinere Potenz von 2 ansehen. Für ein Array, dessen Länge 1000 beträgt, ist die nächstkleinere Potenz von 2 512, was $2^9$‍. Wir können also schätzen, dass ${\log }_{2}1000$‍ eine Zahl größer als 9 und kleiner als 10 ist, oder einen Taschenrechner benutzen, um zu sehen, dass es ungefähr 9,97 ist. Addiert man 1 dazu, erhält man ungefähr 10,97. Im Falle einer Dezimalzahl runden wir ab, um die tatsächliche Anzahl der Schätzungen zu finden. Für ein Array mit 1000 Elementen würde die binäre Suche also höchstens 10 Versuche erfordern.

Für den Sternenkatalog Tycho-2 mit 2,539,913 Sternen ist die nächsthöhere Potenz von 2 gleich $2^{21}$‍ (also 2,097,152), und wir würden höchstens 22 Mal raten müssen. Viel besser als die lineare Suche!

Vergleiche $n$‍ und ${\log }_{2}n$‍ unten:

Im nächsten Tutorial sehen wir, wie Informatiker die Laufzeiten von linearer und binärer Suche mithilfe einer Notation beschreiben, welche den wichtigsten Teil der Laufzeit zusammenfasst und die weniger wichtigen Teile außer Acht lässt.

Dieses Tutorial ist in Zusammenarbeit zwischen den Professoren Thomas Cormen und Devin Bock von Dartmouth Computer Sience und dem Khan Academy Computing Curiculum-Team entstanden und wurde von der KA Deutsch Community übersetzt. Das Tutorial ist unter der Lizenz CC-BY-NC-SA lizenziert.