Suchalgorithmus: Linear oder binär suchen

Der Suchwert ist der Wert, den du finden möchtest. Die lineare Suche beginnt beim ersten Eintrag. Vergleiche ihn mit dem Suchwert. Bei Gleichheit meldest du die gefundene Stelle und stoppst. Sonst prüfst du den nächsten Eintrag. Ist die Liste zu Ende, meldest du „nicht gefunden“.

Für die binäre Suche verwenden wir aufsteigend sortierte Zahlen: Kleinere Werte stehen vor größeren; gleiche Werte dürfen nebeneinander vorkommen. Der Suchbereich ist der Teil der Liste, der noch infrage kommt. Anfangs ist das die ganze Liste. Prüfe den mittleren Eintrag. Gibt es zwei mittlere Einträge, nehmen wir in dieser Lektion den linken. Ist er gleich dem Suchwert, meldest du seine Stelle und stoppst. Ist der Suchwert kleiner, suchst du links von der geprüften Mitte weiter. Ist er größer, suchst du rechts davon weiter. Die geprüfte Mitte gehört nicht mehr zum neuen Suchbereich. Wiederhole diese Schritte, bis du den Wert findest oder der Suchbereich leer ist.

Ein leerer Suchbereich bedeutet „nicht gefunden“. Auch eine von Anfang an leere Liste liefert dieses Ergebnis, ohne einen Eintrag zu prüfen. Kommt der Suchwert mehrfach vor, findet die lineare Suche den ersten Treffer von links. Die binäre Suche kann eine andere passende Stelle liefern.

Wir zählen jeden Vergleich des Suchwerts mit einem Listeneintrag als einen Vergleichsschritt. Das Ergebnis kann „kleiner“, „gleich“ oder „größer“ sein. Wir zählen hier weder einzelne Prüfzeichen eines Programms noch andere Arbeitsschritte.

Bei der linearen Suche braucht ein Treffer am Anfang einen Vergleich. Steht der erste Treffer ganz am Ende oder fehlt der Suchwert, prüfst du jeden Eintrag. Das Maximum, also die größte mögliche Vergleichszahl, entspricht deshalb der Anzahl der Einträge.

Die binäre Suche braucht ebenfalls einen Vergleich, wenn der Suchwert gleich in der zuerst geprüften Mitte steht. Andernfalls fällt mit jedem Schritt ungefähr die Hälfte des bisherigen Suchbereichs weg. Die geprüfte Mitte fällt ebenfalls weg. Deshalb steigt bei einer nicht leeren Liste die maximale Vergleichszahl nur um einen, wenn du die Anzahl der Einträge verdoppelst. Die Tabelle zeigt diesen Unterschied. Bei längeren Listen wächst der Abstand zwischen den beiden Maximalzahlen. Eine einzelne lineare Suche kann trotzdem nach einem Vergleich fertig sein.

Die Vergleichszahlen beschreiben die Suche in einer bereits vorliegenden Liste. Vorheriges Sortieren ist nicht mitgezählt. Weniger Suchvergleiche garantieren auch keine im gleichen Verhältnis kürzere gemessene Suchzeit.

Die lineare Suche funktioniert in sortierten und in ungeordneten Listen. Sie prüft Einträge nacheinander und überspringt vor einem Treffer keinen Eintrag. Deshalb braucht sie keine vorherige Sortierung.

Die binäre Suche braucht für unser Verfahren eine aufsteigend sortierte Liste. Erst diese Ordnung erlaubt den Schluss: Ist der Suchwert kleiner als die Mitte, kann er nicht rechts davon stehen. Ist er größer, kann er nicht links davon stehen. In einer ungeordneten Liste könnten passende Werte in der ausgeschlossenen Hälfte liegen.

Ein Eintrag kann mehrere Angaben enthalten. In der Tabelle gehören zu jedem Heft eine Heftnummer und eine Seitenzahl. Die Heftnummern sind aufsteigend sortiert, die Seitenzahlen sind ungeordnet. Deshalb ist die Liste für eine binäre Suche nach Heftnummern vorbereitet. Für eine binäre Suche nach Seitenzahlen müsstest du die Einträge zuerst nach der Seitenzahl ordnen. Für die lineare Suche ist das nicht nötig.

Wähle also nach der gesuchten Angabe und ihrer Reihenfolge. Wenn du eine ungeordnete Liste erst sortierst, ist das zusätzlicher Aufwand vor der binären Suche. Dieser Aufwand gehört nicht zu unseren gezählten Suchvergleichen.