Bei der sequentiellen Suche wird das Feld in einer Schleife durchlaufen, die dann beendet ist, wenn das Element Suchelement gefunden wird. Im besten Fall (erstes Element ist bereits das Suchelement) wird 1 Schleifendurchlauf benötigt. Im schlechtesten Fall (das Suchelement wird nicht gefunden) wird das gesamte Feld in n Schleifendurchläufen durchlaufen. Im Mittel benötigt man also n/2 Schleifendurchläufe. Daraus ergibt sich eine algorithmische Ordnung
O(n)
Auch hier müssen wir zwischen dem best case und den worst case unterscheiden.
Im best case ist das Element in der "linken Mitte" bereits das gesuchte. Dann wird keine Rekursion durchgeführt. Lediglich ein paar (konstante) Vergleiche und Zuweisungen werden ausgeführt.
Erst durch die Rekursion wird eine (Quasi-)Schleife durchlaufen. Die Anzahl der "Schleifendurchläufe" ergibt sich aus der Tiefe der Rekursion. Da das Feld in jedem Rekursionsschritt längenmässig halbiert wird, wird spätestens nach log2n-Rekursionen entweder das Suchelement gefunden oder die Entscheidung getroffen, dass es nicht enthalten ist. Die algorithmische Ordnung ist daher
O(log2n)
Allerdings muss das Feld sortiert sein. Im Falle eines unsortierten Feldes kommt hier noch einmal ein Sortieraufwand hinzu, der sogar größerer Ordnung ist, als das Suchverfahren selbst. Da die sequentielle Suche auch in unsortierten Feldern mit gleicher Ordnung funktioniert, ist sie dort in jedem Fall das schnellere Verfahren, wenn man den Sortieraufwand mit einkalkuliert.
Ein weiteres Problem der binären Suche ist, dass ich auf die Indizes der Feldelemente direkt zugreifen muss, was insbesondere in (sequentiellen) Listenstrukturen nicht gewährleistet ist. Daher ist auch aus dieser Sicht dort die sequentielle Suche die einzig mögliche. Erst durch andere Speicherarten (Binärbäume) lassen sich dann die Vorteile in der algorithmischen Ordnung ausnutzen.
© Ralph-Erich Hildebrandt, 04. Februar 2005