- Zielwert
- Noch möglich
- Verglichen
- Ausgeschlossen
- Gefunden
Binäre Suche
Die binäre Suche findet einen Wert in einer sortierten Liste, indem sie immer in der Mitte nachsieht. Ist der mittlere Wert zu klein, kann das Ziel nur dahinter liegen; ist er zu groß, nur davor. So oder so fällt die Hälfte des Rests weg. Wählen Sie den gesuchten Wert, gehen Sie die Suche Schritt für Schritt durch und sehen Sie zu, wie der schattierte Bereich schrumpft, bis das Ziel gefunden ist oder nichts mehr übrig bleibt. Drücken Sie „Abspielen“, um die Suche anzusehen, oder gehen Sie mit „Schritt“ und „Zurück“ einen Schritt nach dem anderen durch. Ziehen Sie den Schrittregler, um an eine beliebige Stelle zu springen. Die gestrichelte Linie markiert den gesuchten Wert, und der schattierte Bereich zeigt, wo er noch sein kann. Die binäre Suche braucht eine sortierte Liste, daher wird eine unsortierte Liste zuerst sortiert. Wählen Sie den Wert und die Anzahl der Balken, oder geben Sie eigene Zahlen ein. Ist das Feld ausgewählt, gehen die Pfeiltasten schrittweise vor, die Leertaste startet und pausiert, und Pos1 und Ende springen zum Anfang und zum Ende.
Wie es funktioniert
- Wählen Sie den gesuchten Wert und die Anzahl der Balken. Oder geben Sie eigene Zahlen ein: Die binäre Suche sortiert sie zuerst.
- Drücken Sie „Abspielen“ oder gehen Sie mit „Schritt“ und „Zurück“ einen Schritt nach dem anderen durch. Ziehen Sie den Schrittregler, um an eine beliebige Stelle der Suche zu springen.
- Vergleichen Sie die Kachel „Vergleiche“ mit „Lineare Suche bräuchte“, für einen Wert nahe am Ende oder einen, der fehlt.
So funktioniert die binäre Suche
Merken Sie sich den Teil der sortierten Liste, der das Ziel noch enthalten kann; anfangs ist das die ganze Liste. Sehen Sie sich den Wert in seiner Mitte an. Ist er gleich dem Ziel, sind Sie fertig. Ist er kleiner, kann das Ziel nur dahinter liegen, also machen Sie mit dem Teil nach der Mitte weiter. Ist er größer, mit dem Teil davor. Bleibt nichts übrig, ist das Ziel nicht in der Liste.
Warum sie so schnell ist
Jeder Vergleich halbiert den verbleibenden Teil. Von n Werten bleiben nach k Vergleichen höchstens etwa n/2ᵏ übrig, daher endet die Suche nach höchstens ⌊log₂ n⌋ + 1 Vergleichen: 6 bei 40 Werten, 10 bei 1.000, 20 bei einer Million. Die lineare Suche muss unter Umständen jeden Wert ansehen. Der Haken: Die Liste muss sortiert sein, und sie sortiert zu halten oder erst zu sortieren, kostet ebenfalls.
Häufig gestellte Fragen
Wie funktioniert die binäre Suche?
Sie vergleicht das Ziel mit dem mittleren Wert des Teils einer sortierten Liste, der es noch enthalten kann. Gleich heißt gefunden; sonst fällt die Hälfte weg, die das Ziel nicht enthalten kann, und die Suche geht in der anderen Hälfte weiter, bis das Ziel gefunden ist oder nichts mehr übrig bleibt.
Wie viele Vergleiche braucht die binäre Suche?
Höchstens ⌊log₂ n⌋ + 1 bei einer Liste mit n Werten: 6 bei 40, 10 bei 1.000, 20 bei einer Million. Jeder Vergleich halbiert den Rest.
Warum braucht die binäre Suche eine sortierte Liste?
Weil nur in einer sortierten Liste ein einziger Vergleich verrät, auf welcher Seite das Ziel liegt. In einer unsortierten Liste sagt ein kleinerer Wert in der Mitte nichts darüber, wo das Ziel ist, also lässt sich nichts ausschließen.
Welchen Wert findet sie bei Duplikaten?
Irgendeinen davon, je nachdem, wo die Mitten liegen. Varianten, die nach einem Treffer links oder rechts weitersuchen, finden das erste oder das letzte Vorkommen.
Werden meine Zahlen irgendwohin gesendet?
Nein. Die Suche läuft in Ihrem Browser, und Ihre letzten Einstellungen bleiben im lokalen Speicher dieses Browsers.
Bereit, es auszuprobieren?
Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.
Zum Editor