Aufgabe 07 - Binäre Suche

Aufgabe 07 - Binäre Suche

Worum geht es?

Halbieren statt durchprobieren: Sie implementieren die binäre Suche und vergleichen sie messbar mit der linearen Suche aus der 1. Klasse (siehe Kapitel Algorithmen analysieren).

In dieser Übung üben Sie:

• Implementieren: binäre Suche mit linker/rechter Grenze.
• Vergleichen: Vergleichszahlen beider Suchverfahren gegenüberstellen.
• Argumentieren: die Voraussetzung “sortiert” begründen.

Benötigte Unterlagen

• VS Code, Browser-Konsole.

Arbeitsaufträge

Teil A - Von Hand

1. Spielen Sie das Zahlenraten-Spiel (1-100) mit der Halbierungsstrategie gegen eine Partnerin/einen Partner: Wie viele Versuche brauchen Sie höchstens? Notieren Sie die Versuchsfolge für die gesuchte Zahl 73.
2. Wie viele Versuche wären es bei 1-1000? Begründen Sie ohne Programm.

Teil B - Implementieren

1. binaereSuche(liste, gesucht): liefert den Index oder -1. Arbeiten Sie mit links, rechts und mitte (Math.floor).
2. Testen Sie mit einer sortierten Liste aus 20 Zahlen: erstes Element, letztes Element, Mittelelement, nicht vorhandener Wert.
3. Bauen Sie einen Vergleichszähler ein (wie in Aufgabe 18 der 1. Klasse bei der linearen Suche).

Teil C - Duell der Verfahren

1. Erzeugen Sie eine sortierte Liste mit 10 000 Zahlen (Schleife).
2. Suchen Sie denselben Wert mit linearer und binärer Suche und geben Sie beide Vergleichszahlen aus.
3. Füllen Sie eine Tabelle für Listengrößen 100, 1 000, 10 000: Vergleiche linear (schlimmster Fall) vs. binär.
4. Was passiert, wenn Sie die binäre Suche auf eine unsortierte Liste loslassen? Probieren Sie es aus und erklären Sie das Ergebnis.

Abgabe

suche.js mit beiden Verfahren, der Vergleichstabelle und den Antworten als Kommentar.