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

Aus VoWi
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)

  1. 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)

  1. Bereichsgrenzen:

Element an der Stelle 2: 9

Element 9 = 9 - Element gefunden, Suche beendet


Im Allgemeinen braucht es Maximal