Zum Inhalt
Alle Apps

Binäre vs. lineare Suche

Über diese App

Warum Halbieren gewinnt: Binäre und lineare Suche laufen nebeneinander über dasselbe sortierte Array, mit Live-Schrittzählern. Bei 128 Elementen findet binär in ~6 Vergleichen, was linear ~106 kostet — der Vorsprung wächst dramatisch mit n (O(log n) vs. O(n)). Widerlegt „binär ist nur ein bisschen schneller".

Warum Halbieren so schnell ist

Die lineare Suche prüft ein Element nach dem anderen von links und braucht im schlechtesten Fall n Vergleiche. Die binäre Suche setzt ein sortiertes Array voraus: Sie vergleicht das Ziel mit dem mittleren Element und verwirft je nach Ergebnis die linke oder die rechte Hälfte. Mit jedem Vergleich halbiert sich der Suchraum, deshalb genügen höchstens etwa log₂(n) + 1 Vergleiche. Bei 128 Elementen sind das 8 statt bis zu 128, bei einer Million rund 20 statt einer Million.

Was die App zeigt

Zwei Karten nebeneinander: links die binäre Suche, die mit dem jeweils verglichenen Mittelbalken den Suchraum halbiert, rechts die lineare Suche, die von links jedes Element prüft. Über beiden steht der gesuchte Wert. Ein Werte-Panel zeigt live n, log₂(n), die Schritte beider Verfahren und den Faktor, um wie viel mehr Schritte die lineare Suche braucht.

Selbst ausprobieren

Wähle die Array-Größe 8, 16, 32, 64 oder 128, setze ein Zufallsziel oder klicke ein Ziel an und starte beide Suchen gleichzeitig oder Schritt für Schritt, in einstellbarem Tempo. Setze das Ziel ganz nach rechts, um den schlechtesten Fall der linearen Suche zu sehen, und verdopple dann n: Die binäre Suche braucht nur einen Schritt mehr.

Häufige Fragen

Wie funktioniert die binäre Suche?
Im sortierten Array wird das mittlere Element mit dem Ziel verglichen. Ist das Ziel kleiner, sucht man in der linken Hälfte weiter, ist es größer, in der rechten. Das wiederholt sich, bis das Ziel gefunden ist oder der Suchbereich leer ist.
Welche Laufzeit hat die binäre Suche?
O(log n). Weil sich der Suchbereich mit jedem Vergleich halbiert, braucht man für n Elemente höchstens etwa log₂(n) + 1 Vergleiche. Die lineare Suche braucht O(n), im schlechtesten Fall also n Vergleiche.
Wann kann man die binäre Suche nicht verwenden?
Wenn die Daten nicht sortiert sind oder kein schneller Zugriff auf ein beliebiges Element möglich ist, etwa bei einer verketteten Liste. Für einmaliges Suchen in unsortierten Daten ist die lineare Suche günstiger, als erst zu sortieren.
Was zeigt die App zur binären Suche?
Binäre und lineare Suche laufen nebeneinander auf demselben Array mit 8 bis 128 Elementen. Schrittzähler, log₂(n) und der Faktor zwischen beiden Verfahren werden live angezeigt; Ziel und Tempo stellst du selbst ein.

Fach: Informatik

Mehr aus Informatik

Eine VisuApp von heyprof: interaktiv, kostenlos im Browser, ohne Anmeldung. Was ist eine VisuApp? · Alle Apps