Kapitel 6. Suchverfahren
Sequentielle Suche
Binäre Suche
1. Falls Liste leer ist, endet die Suche erfolglos. Sonst: Betrachte Element der Liste an mittlerer Position m.2. Falls K = Schlüsselwert dieses Elementes, dann ist das gesuchte Element gefunden .
Binäre Suche (2)
Kosten
Fibonacci-Suche
- Element an der Position i = F k-2 wird mit dem Schlüssel K verglichen
Sprungsuche
Einfache Sprungsuche
Optimale Sprungweite
Exponentielle Suche
Sind in der sortierten Liste nur positive, ganzzahlige Schlüssel ohne Duplikate gespeichert, wachsen Schlüsselwerte mindestens so stark wie die Indizes der Elemente.
Interpolationssuche
Sinnvoll, wenn der Schlüsselwert im betreffenden Bereich einigermaßen gleichverteilt ist
Anmerkungen zur Implementierung in C
Rekursive Definition eines Strukturtyps
Verwendung von typedef
E-Mail: der@informatik.uni-leipzig.de
Homepage: http://www.informatik.uni-leipzig.de/~der