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.

Das Problem 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

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

🕳

Lückenhaft

Links fehlen noch folgende wichtige Informationen:

Laufzeit

Hilf dem KGS-Wiki, indem du sie recherchierst und einfügst.