Simulic
Deutsch

Lineare Suche und binäre Suche – Vergleiche zählen

InformatikAlgorithmen und ProblemlösenAlter 12–13

Simulic.comWird geladen …

Mit meiner Klasse nutzen

Dasselbe Array und derselbe Suchwert durchlaufen nebeneinander die lineare Suche (vom Anfang an durchgehen) und die binäre Suche (Bereich in einem sortierten Array halbieren). Die Lernenden klicken auf „Schritt“ oder „Abspielen“ und sehen das gerade verglichene Feld, den ausgeschlossenen Bereich und die Anzahl der Vergleiche jedes Algorithmus; ein Klick auf ein Feld ändert den Suchwert, und wenn die Sortierung ausgeschaltet wird, zeigt sich, warum die binäre Suche nicht mehr funktioniert.

Lektion: Algorithmus der linearen Suche; Algorithmus der binären Suche

Was sie zeigt

Die lineare Suche prüft die Elemente nacheinander vom Anfang an und braucht im ungünstigsten Fall so viele Vergleiche, wie es Elemente gibt. Die binäre Suche vergleicht den Suchwert mit dem mittleren Element eines sortierten Arrays und verwirft die Hälfte, die ihn nicht enthalten kann; sie braucht daher höchstens etwa log₂n + 1 Vergleiche, bei sechzehn Elementen nur fünf. Das Zählen der Vergleiche beider Algorithmen auf demselben Array zeigt, warum die binäre Suche bei langen Listen gewinnt und warum sie vollständig auf sortierte Daten angewiesen ist.

So funktioniert es

Stellen Sie Algorithmus auf Beide (vergleichen), wählen Sie die Anzahl der Elemente und klicken Sie auf Schritt, um jeden Vergleich zu verfolgen: die markierte Zelle, die Marken low, mid und high und den ausgeschlossenen Teil des Arrays. Klicken Sie auf eine Zelle, um den Suchwert zu ändern, oder nutzen Sie Abspielen für einen ganzen Durchlauf. Testen Sie einen Wert nahe dem Anfang und schalten Sie dann Array aufsteigend sortiert aus.

Einstellbare Parameter

  • Anzahl der Elemente 5–20
  • Suchwert (0 = zufällig aus dem Array wählen) 0–99
  • Algorithmus Beide (vergleichen), Lineare Suche, Binäre Suche
  • Array aufsteigend sortiert
  • Ablaufgeschwindigkeit 1–5 Schritte/s

Fragen zum Erkunden

  1. Wie viele Vergleiche braucht die binäre Suche höchstens, um einen Wert in einem Array mit 16 Elementen zu finden?
  2. Bei welchen Suchwerten braucht die lineare Suche weniger Vergleiche als die binäre Suche?
  3. Warum lässt sich die binäre Suche nicht mehr verwenden, wenn das Array nicht sortiert ist?

Ähnliche Simulationen