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