Beim linearen (sequenziellen) Suchen werden alle Elemente einer Datenstruktur durchlaufen und mit dem Suchelement verglichen. Eine lineare Suche ist erforderlich, wenn die Datenstruktur in einem nicht-sortiertem Format vorliegt. Sie ist sehr zeitaufwendig, da im schlechtesten Fall alle Elemente mit dem Suchelement verglichen werden müssen, d.h. daß bei n Elementen in der Datenstruktur n Vergleiche ausgeführt werden müssen, im Mittel immer noch (n + 1) / 2 Vergleiche.

Binäres Suchen

Das binäre Suchen kann ein sortiertes Array effizient nach einem gesuchten Wert durchsuchen. Idee ist die fortwährende Halbierung des Suchintervalls unter Ausnutzung der Sortierung. Wir setzen hier aufsteigende Sortierung voraus. Die Grafik zeigt den Indexbereich eines Arrays der Länge n. Der grüne Suchbereich wird jeweils durch Vergleich des Suchwertes mit dem Wert in der Intervallmitte halbiert, wodurch rechts und oder links vom Suchbereich Intervalle mit kleineren bzw. größeren Werten enstehen, die nicht mehr abgesucht zu werden brauchen. Zum Schluß gilt left > right, der Suchbereich ist leer.

 

Etwa ab einer Größenordnung von n = 8 sollte das binäre Suchen dem linearen Suchen überlegen sein. Bei größeren n wächst der Unterschied schnell an (exponentiell).

In m Schleifendurchläufen werden 2*m - 1 Elemente abgesucht.

Ist umgekehrt n, die Anzahl der abzusuchenden Elemente, gegeben, so braucht man höchstens 2*log(n) + 1 Schleifendurchläufe.

Der Logarithmus zu Basis 2 ist auf Taschenrechnern üblicherweise nicht vorhanden. Man behelfe sich bei Bedarf mit der Formel:

2*log(n) = log(n) / log(2)

wobei als log, sowohl der 10´er Logarithmus, als auch der natürliche Logarithmus zur Basis e genommen werden kann. Letzterer wird meist mit ln statt mit log bezeichnet.

Weitere Suchverfahren

Es existieren weitere Suchverfahren, die u. U. effizienter als die binäre Suche arbeiten - dies ist jedoch abhängig von weiteren Eigenschaften der zu durchsuchenden Liste (bspw. Gleichverteilung). So kann bspw. die Interpolationssuche schneller, aber auch langsamer als die binäre Suche sein, gleiches gilt für die exponentielle Suche.