Übung Binärsuche (sucheIterativBinär) ◦ ?

Lernziele

- Binäre Suche
- Rekursion

Wiederholungsfragen

1. Die
binäre Suche ...

1. halbiert das Datenfeld solange, bis das gesuchte Element gefunden ist.

2. betrachtet hintereinander Element für Element, bis das gesuchte Element gefunden ist.

3. durchsucht ein Datenfeld mit einer For-Next-Schleife.

2. Der
Operator \ ...

1. berechnet den Rest einer ganzzahligen Division (Bsp. 5\2 = 1).

2. dividiert ganzzahlig (Bsp. 5\2 = 2).

3. dividiert (Bsp. 5\2=2.4).

3. Wodurch unterscheiden sich
sequentielles und binäres?

1. Die sequentielle Suche ist immer langsamer als die binäre Suche.

2. Für die binäre Suche muss das Datenfeld sortiert sein, für die sequentielle Suche nicht.

3. Für die sequentielle Suche muss das Datenfeld sortiert sein, für die binäre Suche nicht.

Implementation

1. Suchen Sie wie in der Tabelle von Binärsuche:

> Suchen Sie EMIL:

> Nummer | 1 | 2 | 3 | 4 | 5 | 6 | 7
> Läufer(Nr) | ANNA | BERTA | EMIL | PETER | RICHARD | TITUS | VOLKER
> 1. Schritt | ............ | ............ | ............ | ............ | ............ | ............ | ............
> 2. Schritt | ............ | ............ | ............ | ............ | ............ | ............ | ............
> 3. Schritt | ............ | ............ | ............ | ............ | ............ | ............ | ............

> Suchen Sie SAMUEL:

> Nummer | 1 | 2 | 3 | 4 | 5 | 6 | 7
> Läufer(Nr) | ANNA | BERTA | EMIL | PETER | RICHARD | TITUS | VOLKER
> 1. Schritt | ............ | ............ | ............ | ............ | ............ | ............ | ............
> 2. Schritt | ............ | ............ | ............ | ............ | ............ | ............ | ............
> 3. Schritt | ............ | ............ | ............ | ............ | ............ | ............ | ............
> 4. Schritt | ............ | ............ | ............ | ............ | ............ | ............ | ............

1. Beschreiben Sie den Algorithmus der binären Suche in eigenen Worten (Schritt für Schritt) und vergleichen Sie Ihre Formulierungen mit dem Algorithmus des Hilfethemas Datenfelder.

2. Die binäre Suche lässt sich nicht nur rekursiv, sondern auch in Form einer Schleife (iterativ) programmieren. Vervollständigen Sie sucheIterativBinärSkelett.xls und beantworten Sie die folgende Fragen:

   - Wie oft muss die Schleife durchlaufen werden?
   - Welche Schleife ist geeignet und warum (For-Next, For-Each, Do-While)?
   - Wann ist die Suche fertig, das heisst, wann kann die Schleife verlassen werden?
   - Welche Variablen benötigen Sie?

Zusatzaufgabe

Nach einem Klick auf die Schaltfläche »Q uadrat zeichen des Beispiels QuadratProgrammiertDialog.xls soll eine Passwort-Prozedur garantieren, dass nur Berechtigte ein Quadrat zeichnen können. Die Berechtigung soll durch eine binäre Suche in einem Datenfeld von Passwörtern nachgeschlagen werden. Implementieren Sie Ihre Lösung in einer Arbeitsmappe “QuadratDialogPasswort.xls”.

sucheIterativBinär.xls