TU Wien:Algorithmen und Datenstrukturen 1 VU (Raidl)/Übungen SS09/Beispiel 14
Zur Navigation springen
Zur Suche springen
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 -Notation?
Lösung für die Suche nach 9[Bearbeiten | Quelltext bearbeiten]
{1, 9, 10, 12, 13, 14, 15, 20, 40, 80} (n = 10)
- Bereichsgrenze:
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)
- Bereichsgrenzen:
Element an der Stelle 2: 9
Element 9 = 9 - Element gefunden, Suche beendet
Im Allgemeinen braucht es Maximal