Binäre Suche: die Suche halbieren — Informatik, 7–10
Wenn eine Liste schon sortiert ist, musst du nicht jeden Eintrag einzeln prüfen. Die binäre Suche schaut in die Mitte, wählt die Hälfte aus, in der die Antwort liegen kann, und wiederholt das, bis sie gefunden oder ausgeschlossen ist.
Die Möglichkeiten immer halbieren
Stell dir eine geheime Zahl in einer geordneten Reihe vor. Statt bei der ersten Zahl zu beginnen, fragst du nach der mittleren. Ist dein Ziel größer, streichst du die untere Hälfte; ist es kleiner, die obere. Jede Antwort entfernt ungefähr die Hälfte der Möglichkeiten, sodass die Suche schnell klein wird.
Warum nicht jeden Eintrag prüfen?
Am Anfang zu suchen reicht bei einer kurzen Liste, wird aber bei Tausenden oder Millionen geordneter Einträge langsam. Die binäre Suche nutzt die Ordnung als Hinweis, statt sie zu verschenken. Sie entstand aus der sinnvollen Frage: Wie können wir mit einer Prüfung möglichst viele falsche Stellen ausschließen?
73 in einer Liste finden
Die geordnete Liste lautet 12, 25, 31, 44, 58, 73, 81, 90. Zuerst prüfst du die Mitte: 44. Weil 73 größer ist, behältst du 58, 73, 81, 90. In dieser Gruppe prüfst du die Mitte: 73. Nach zwei Prüfungen ist das Ziel gefunden, statt alle acht Zahlen von vorn anzusehen.
Die Ordnung ist entscheidend
Es wirkt vernünftig, bei jeder Liste die Mitte anzusehen, weil die Mitte wie eine gute Abkürzung erscheint. Aber bei 12, 90, 25, 73, 44, 81, 31, 58 verrät dir 44 nicht, in welcher Hälfte 73 liegt. Binäre Suche funktioniert nur, wenn die Liste nach dem Merkmal geordnet ist, das du vergleichst.
Dinge schnell finden
Ein Wörterbuch ist alphabetisch geordnet, deshalb kannst du ungefähr in der Mitte aufschlagen und die Suche nach einem Wort verkleinern. Programme nutzen dieselbe Strategie bei geordneten Namen, Zahlen und Datensätzen. Das hilft bei einer großen, schon sortierten Liste; sie vorher zu sortieren kann aber zusätzliche Arbeit kosten.
Weiter erkunden
Andere Sprachen
MyLeoNes™ wird geladen…