Suchen

Du suchst ständig: einen Namen im Chatverlauf, ein Lied in deiner Playlist, ein Wort im Wörterbuch. Auch Computer suchen andauernd, nur in viel größeren Listen. Wie sie das clever anstellen, schauen wir uns jetzt an.

Lineare Suche: der Reihe nach

Die einfachste Idee: Du gehst die Liste von vorne nach hinten durch und prüfst jeden Eintrag, bis du den richtigen findest. Das heißt lineare Suche. Sie funktioniert immer, auch wenn die Liste durcheinander ist. Aber sie kann dauern: Steht der gesuchte Eintrag ganz hinten in einer Liste mit 1000 Einträgen, brauchst du 1000 Schritte.

Binäre Suche: immer halbieren

Wenn die Liste sortiert ist, geht es viel schneller. Denk an ein Telefonbuch: Du suchst 'Meier' und schlägst es in der Mitte auf. Steht dort 'Schulz', weißt du sofort, dass 'Meier' in der vorderen Hälfte liegt. Die hintere Hälfte kannst du komplett wegwerfen. Dann halbierst du die vordere Hälfte wieder, und so weiter. Das ist die binäre Suche: Mit jedem Schritt wird die Liste halbiert.

Schritte zählen

Ein Schritt heißt hier immer: Du schaust dir einen Eintrag an und vergleichst ihn mit dem gesuchten. Der Unterschied zwischen beiden Verfahren ist riesig. Bei 1000 Einträgen braucht die lineare Suche schlimmstenfalls 1000 Schritte. Die binäre Suche halbiert: 1000, 500, 250, 125 und so weiter. Nach etwa 10 Halbierungen ist nur noch ein Eintrag übrig. 10 Schritte statt 1000! Je größer die Liste, desto deutlicher gewinnt das Halbieren.

Die Voraussetzung: sortiert

Die binäre Suche hat einen Haken: Sie funktioniert nur, wenn die Liste sortiert ist. Nur dann verrät dir der Blick in die Mitte, in welcher Hälfte du weitersuchen musst. In einer unsortierten Liste bleibt dir nur die lineare Suche. Deshalb ist Sortieren so wichtig, und genau darum geht es im nächsten Thema.