Binäre Suche

Visualisierung der binären Suche. Gesucht ist das Element mit der Nummer 27

Die binäre Suche ist ein Algorithmus, um in sortierten (!) Listen möglichst effizient nach Einträgen suchen zu können. Eng verwandt mit diesem Algorithmus ist der Suchbaum, eine Datenstruktur, die dieses Problem auf eine andere Art und Weise angeht.

Motivation

Das Problem beim Suchen ist, dass man in einer unsortierten Liste nur auf eine Art und Weise nach Einträgen suchen kann: indem man jedes einzelne Element nacheinander betrachtet. In einer Liste mit $n$ Elementen muss man also schlimmstenfalls $n$ Elemente betrachten, um das gesuchte zu finden. Das ist bei extrem langen Listen von Nachteil.

Deswegen bietet es sich an, die Liste zu sortieren und das Prinzip der binären Suche anzuwenden.

Die Idee

Man betrachtet zunächst das Element, das in der Mitte der Liste steht. Nun gibt es drei mögliche Fälle:

1. Das mittlere Element ist genau das gesuchte. Hurra! Wir haben es gefunden!
2. Das mittlere Element ist größter als das gesuchte. Dann können wir die ganze zweite Hälfte der Liste schon ignorieren. Denn alles, was in dieser zweiten Hälfte steht, ist größer als das mittlere Element (weil die Liste ja sortiert ist) und damit auch größer als das gesuchte Element. Wir können uns also in unserer Suche auf die erste Hälfte der Liste beschränken und diese Hälfte weiter binär durchsuchen.
3. Das mittlere Element ist kleiner als das gesuchte. Dann können wir die ganze erste Hälfte der Liste schon ignorieren. Denn alles, was in dieser ersten Hälfte steht, ist kleiner als das mittlere Element (weil die Liste ja sortiert ist) und damit auch kleiner als das gesuchte Element. Wir können uns also in unserer Suche auf die zweite Hälfte der Liste beschränken und diese Hälfte weiter binär durchsuchen.

Der Algorithmus

Gegeben seien eine Liste L und ein gesuchtes Element g. Für diesen Algorithmus verwenden wir die zwei Variablen start und ende, die den Beginn und das Ende des zu suchenden Bereichs markieren. Jedes Mal, wenn der Algorithmus einen nicht passenden Wert betrachtet, wird eine dieser beiden Variablen verändert, um den Suchbereich einzugrenzen.

graph TD start(("Start")) --> s1["setze <code>start</code> auf 0"] --> s2["setze <code>ende</code> auf die Länge von <code>L</code>-1"] --> s3["setze <code>mitte</code> auf (<code>start</code>+<code>ende</code>)/2, abgerundet"] --> w{"<code>L[mitte]</code> = <code>g</code>?"} --ja--> out[/"Gib <code>mitte</code> aus"/] --> ende(("Ende")) w --nein--> i{"<code>L[mitte]</code> > <code>g</code>?"} --ja--> s4["setze <code>ende</code> auf <code>mitte</code>-1"] --> s5["setze <code>mitte</code> auf (<code>start</code>+<code>ende</code>)/2, abgerundet"] --> w i --nein--> s6["setze <code>start</code> auf <code>mitte</code>+1"] --> s5

Laufzeit

Dieser Algorithmus ist extrem schnell. Man kann sich das am besten bewusst machen, indem man kurz durchspielt, wie lang die Listen sein dürfen, damit man garantiert nach $x$ Versuchen einen Treffer landet:

1 Versuch

Wenn man nach einem Versuch sicher einen Treffer landen möchte, darf die Liste nur ein Element enthalten:

1

2 Versuche

Wenn man nach zwei Versuchen sicher einen Treffer landen möchte, darf die Liste drei Elemente enthalten: beim ersten Versuch betrachtet man das mittlere, beim zweiten Versuch dann eins der äußeren:

2

1

2

3 Versuche

Wenn man nach drei Versuchen sicher einen Treffer landen möchte, darf die Liste sieben Elemente enthalten: beim ersten Versuch betrachtet man das mittlere, beim zweiten Versuch hat man dann eine der Dreier-Teillisten vor sich, die man mit zwei Versuchen durchsucht bekommt.

3

2

3

1

3

2

3

4 Versuche

Wenn man nach vier Versuchen sicher einen Treffer landen möchte, darf die Liste fünfzehn Elemente enthalten:

4

3

4

2

4

3

4

1

4

3

4

2

4

3

4

Es kristallisiert sich ein Muster heraus: bei jedem weiteren Versuch wächst die Länge der Liste um das Doppelte plus 1: $1\cdot 2+1=3$, $3\cdot 2+1=7$, $7\cdot 2+1=15$ und so weiter. Allgemein lässt sich festhalten: eine Liste, die in $x$ Versuchen durchsucht werden kann, darf bis zu $2^{x}-1$ Elemente enthalten.

𝒪-Notation

Die lineare Suche, die bei unsortierten Listen angewendet werden muss, hat eine Laufzeit von ${\mathcal {O}}(n)$, das heißt, die Laufzeit wächst linear mit der Länge der Liste: Verdoppelt sich die Länge der Liste, verdoppelt sich auch die Anzahl der Elemente, die man schlimmstenfalls betrachten muss.

Die binäre Suche hat eine Laufzeit von ${\mathcal {O}}(\log _{2}(n))$, das heißt, die Laufzeit wächst logarithmisch mit der Länge der Liste. In anderen Worten: Wenn sich die Länge der Liste verdoppelt, erhöht sich die Anzahl der Elemente, die man schlimmstenfalls betrachten muss, um 1.

Zum Weiterlesen

• "Binäre Suche" auf inf-schule.de 🇩🇪
• "Arrays" auf VisuAlgo.net 🇬🇧🇨🇳🇮🇩 (oben Sorted und dann unten links Special → Search auswählen)