Suche in ungeordneten linearen Listen
Sequentielle Suche
- durchlaufe Liste sequentiell bis Schlüssel gefunden oder Listenende erreicht ist
- linearer Suchaufwand: O(n)
Suche in geordneten linearen Listen
Sequentielle Suche
- durchlaufe Liste (aufsteigend) solange Suchschlüssel größer aktueller Schlüssel und Listenende nicht erreicht
- linearer Suchaufwand: O(n)
Binäre Suche
- V1
- Intervallunterteilung bis Intervallgröße = 1
- Aufwand: O(log²n)
- kein Abbruch, selbst wenn Schlüssel gefunden wird
- V2
- Divide & Conquer
- auf Pos. bezogen mittlere Element suchen und mit Schlüssel vergleichen
- anschließend ggfs. Teilbereich weiter durchsuchen
- zmin = 1 (sofortiger Fund)
- zmax = h (Höhe des Baumes) –> Herleitung für Examen!!! (folgt)
- Aufwand worst-case: O(logn)
Sprungsuche / Intervallsuche
- sortierter Datenbestand in Sprüngen überqueren
- Abschnitt lokalisieren
- einfache Sprungsuche
- konstante Sprungweite
- sequentielle Suche im Sprungbereich
- binäre
- konstante Sprungweite
- binäre Suche im Sprungbereich
- Aufwand: O(√n) = O(n^½) – zwischen sequentieller und binärer Suche
Related Images: