TU Wien:Algorithmen und Datenstrukturen 1 VU (Raidl)/Übungen SS09/Beispiel 14

Gegeben ist ein Feld, das die folgenden Elemente in der angegebenen Reihenfolge enthält:

{1,9,10,12,13,14,15,20,40,80}

Führen Sie in dem angegebenen Feld eine Binärsuche nach dem Schlüssel 9 durch. Geben Sie dabei in jedem Schritt die jeweiligen Bereichsgrenzen an.

Wie hoch ist der durchschnittliche Aufwand der Binärsuche in Abhängigkeit der Anzahl n der Elemente in einer sortierten Folge in $\theta$-Notation?

Lösung für die Suche nach 9

{1, 9, 10, 12, 13, 14, 15, 20, 40, 80} (n = 10)

1. Bereichsgrenze: $\lfloor {\frac {n+1}{2}}\rfloor =\lfloor {\frac {10+1}{2}}\rfloor =5$

Element an der Stelle 5: 13

Element 13 > 9 (daher ist die gesuchte Zahl im linken Teil)

Neue Teilfolge ist von 0 bis Bereichsgrenze - 1

{1, 9, 10, 12} (n = 4)

1. Bereichsgrenzen: $\lfloor {\frac {n+1}{2}}\rfloor =\lfloor {\frac {4+1}{2}}\rfloor =2$

Element an der Stelle 2: 9

Element 9 = 9 - Element gefunden, Suche beendet

Im Allgemeinen braucht es Maximal $\theta (log_{2}n)$