Deutsch

Suchen: lineare und binäre Suche

MittelschuleInformatikExakte Suche in einem sortierten Array eindeutiger gerader Ganzzahlen, nullbasierte Indizes

Schalte dieses Lernlabor mit einem Zugangspass frei

Mit einem Zugangspass erhältst du Zugriff auf alle Simulationen der Website, einschließlich des Präsentationsmodus für den Unterricht. Die Unterrichtsmaterialien unten bleiben für alle kostenlos.

Zugangspässe ansehenIch habe bereits einen Zugangspass

Einmalige Zahlung, kein Abonnement.

Über dieses Experiment

Suchen Sie nach demselben Zielwert mit der linearen Suche und der binären Suche nebeneinander. In jedem Schritt wird in jedem noch nicht abgeschlossenen Algorithmus ein Vergleich durchgeführt. Die binäre Suche prüft die Mitte ihres verbleibenden sortierten Intervalls; die lineare Suche rückt jeweils um eine Position vor. Wählen Sie einen ungeraden Zielwert, um zu sehen, wie beide Algorithmen ohne Treffer beendet werden.

Lernziele

  • Verfolgen Sie das Kandidatenintervall und den Mittelpunkt bei der binären Suche
  • Vergleichen Sie die Anzahl der Vergleiche bei linearer und binärer Suche
  • Erklären Sie, warum die binäre Suche sortierte Daten erfordert und mit nicht vorhandenen Zielwerten umgehen kann

Anleitung

  1. 1Suchen Sie im Standardarray nach 32 und führen Sie jeweils einen Vergleich aus.
  2. 2Beachten Sie, wann die binäre Suche beendet wird, und fahren Sie dann fort, bis die lineare Suche beendet wird.
  3. 3Wählen Sie einen ungeraden Zielwert wie 31. Untersuchen Sie, wie die binäre Suche ein leeres Intervall erreicht.
  4. 4Ändern Sie die Arraylänge und suchen Sie nach ihrem letzten Wert. Vergleichen Sie die Grenzen im Worst Case.

Das Modell

Mittelpunkt der binären Suche für inklusive untere und obere Indizes
Obere Schranke für Wertvergleiche bei der binären Suche
Vergleiche im Worst Case für die dargestellte lineare Suche

Annahmen

  • Das Array enthält aufsteigend sortierte, eindeutige gerade Ganzzahlen 2, 4, ..., 2n. Die Indizierung beginnt bei null.
  • Ein Wertvergleich ist ein einzelner Drei-Wege-Vergleich mit dem Zielwert. Indexberechnungen und Schleifenprüfungen werden nicht mitgezählt.
  • Bei einer erfolglosen Suche durchsucht die lineare Suche das gesamte Array, ohne die Sortierung für eine Optimierung mit vorzeitigem Abbruch zu nutzen.
  • Jede Zeile bleibt in ihrem abgeschlossenen Zustand, während die andere Suche weiterläuft. Das aktuelle Kandidatenintervall wird angezeigt, bevor das Ergebnis des aktuellen Vergleichs angewendet wird.

Im Unterricht ausprobieren

  1. Q1Warum darf die binäre Suche nach einem einzigen Vergleich die Hälfte der verbleibenden Positionen ausschließen?
  2. Q2Wie viele Vergleiche sind bei jeder Methode nötig, um den letzten Wert in einem Array mit 32 Werten zu finden?
  3. Q3Was geht schief, wenn dieselbe Mittelpunktregel auf ein unsortiertes Array angewendet wird?

Häufig gestellte Fragen

Warum scheitert die binäre Suche bei einem ungeraden Zielwert?

Jeder Array-Eintrag ist gerade. Ein ungerader Zielwert kann daher nie gefunden werden. Das Kandidatenintervall wird schließlich leer und der Algorithmus meldet, dass der Wert nicht gefunden wurde.

Warum bewegt sich eine Zeile nicht mehr?

Diese Suche ist bereits abgeschlossen. Beim schrittweisen Fortfahren wird der andere Algorithmus weiter ausgeführt, damit die Gesamtvergleichskosten verglichen werden können.