|
Die Suchzeit kann gegenüber der sequentiellen Suche verringert werden, indem man ein sortiertes Feld durchsucht. Das Feld wird in zwei Hälften geteilt, und festgestellt in welcher Hälfte des Feldes sich der gesuchte Datensatz befindet. Diese Methode wird dann rekursiv angewandt, bis nur mehr ein Datensatz übrig ist. Dieser kann der gesuchte sein, oder den Datensatz mit dem gesuchten Schlüssel gibt es nicht. Im Beispiel wird nach der Zahl 13 gesucht:
Binäre Suche erfordert sowohl für erfolgreiche als auch für erfolglose Suche niemals mehr als lg(N+1) Vergleiche.
Dies gilt, weil bei jedem Schritt die Anzahl der Datensätze halbiert wird. Ein Problem entsteht bei nicht eindeutigen Schlüsseln. Wenn während der Suche ein gesuchter Datensatz gefunden wird, müssen dann nämlich auch dessen Nachbarn durchsucht werden.
Die Folge der Vergleiche ist beim binären Suchen vorbestimmt, und kann in einem binären Baum dargestellt werden. Später werden noch Algorithmen beschrieben, die speziell konstruierte Baumstrukturen zur Steuerung der Suche benötigen.
2.1 Interpolationssuche (interpolation search)
Diese stellt eine mögliche Verbesserung dar. Hier versucht man genauer zu erraten, wo sich das gesuchte Element befindet. Dies erinnert an die Suche in einem Telefonbuch, wo man eher vorne zu suchen beginnt, wenn der gesuchte Name mit einem B beginnt. Im Beispiel wird wieder nach der 13 gesucht:
Interpolationssuche erfordert für erfolgreiche aber auch für erfolglose Suche niemals mehr als lg[lg(N+1)] Vergleiche.
Die Interpolationssuche ist besonders für große, gleichmäßig verteilte Felder geeignet, da z. B. für eine Milliarde Elemente nur maximal 5 Schritte erforderlich wären. Ein Nachteil ist, das die Interpolationssuche bei einer sehr ungleichmäßigen Verteilung hereingelegt werden kann. Bei kleinen Feldern ist auch der Vorteil der durch die Interpolation entsteht sehr gering.
|
