Binäre Suche

Wir wissen bereits, wie wir in einem Array nach einem bestimmten Element suchen. Hier haben wir die Lineare Suche kennen gelernt, bei der wir ganz stur das Array durchlaufen und immer prüfen, ob wir den gesuchten Wert gefunden haben. Diese Art der Suche ist aber sehr ineffizient und kann sehr lange dauern, wenn das Array groß ist.

Zum Glück gibt es Such-Algorithmen, die wesentlich effizienter und damit schneller zum Ziel kommen. Das entscheidende dabei: Das Array muss sortiert sein! Nicht nur Menschen, sondern auch digitale Geräte finden in einer sortierten Liste das Gesuchte wesentlich schneller, wenn man einen guten Algorithmus hat.

Algorithmus: So funktioniert die Binäre Suche

 Die binäre Suche funktioniert im Wesentlichen so: Wir teilen das Array in der Mitte und prüfen dann, ob wir in der linken oder in der rechten Hälfte weitersuchen müssen. Das machen wir dann mit der ausgewählten Hälfte genauso, bis wir den gesuchten Wert gefunden haben oder feststellen, dass der Wert nicht vorhanden ist. Wie wir das Teilen und Suchen genau realisieren, wird im Folgenden beschrieben:

Beispiel: Wir suchen die Zahl 9

10 > 9 => Wir müssen links suchen!

Wir müssen also links suchen! Wie sagen wir jetzt dem Computer, dass er links suchen soll? Ganz einfach: Wir verändern den Wert für indexEnde:

Jetzt berechnen wir die Mitte neu:

Jetzt geht es wieder von Anfang los: Wir überprüfen, ob wir die Zahl schon gefunden haben oder weiter links bzw. weiter rechts suchen müssen!

5 < 9 => Wir müssen rechts suchen!

Um weiter rechts zu suchen, verändern wir indexAnfang:

Jetzt berechnen wir die Mitte neu:

array[indexMitte] ist das gesuchte Element! Wir haben es gefunden!

Struktogramm: Ein erster Versuch

In der Schleife stimmt etwas noch nicht! Wann wird die Schleife denn eigentlich abgebrochen? Klar, dann wenn gefunden den Wert true annimmt, wir das gesuchte Element also gefunden haben.

Was passiert aber, wenn das gesuchte Element gar nicht im Array vorhanden ist? Dann nimmt gefunden ja nie den Wert true an! Wir müssen also eine Möglichkeit finden, es zu erkennen, falls der gesuchte Wert nicht vorhanden ist.

Schauen wir uns dieses an einem Beispiel an:

Beispiel: Wir suchen die Zahl 8!

10 > 8 => Wir müssen links suchen!

5 < 8 => Wir müssen rechts suchen!

9 > 8 => Wir müssen links suchen!

Struktogramm: Zweiter Versuch

Wir ändern die Abbruchbedingung in unserem Struktogramm, so dass die Schleife verlassen wird, sobald wir erkennen, dass wir den gesuchten Wert nicht finden können:

Ein letztes Problem: Runden!

Ein Problem ist uns noch gar nicht aufgefallen: Bei der Berechnung von indexMitte kann es sein, dass wir eine Kommazahl erhalten!

Beispiel:

=> indexMitte = (indexAnfang + indexEnde) / 2 = (1 + 6) / 2 = 3,5

Struktogramm Binäre Suche - Vollständige Version

Wir nehmen die letzten Änderungen an unserem Struktogramm vor:

Aufgaben: Binäre Suche anwenden

Erklärvideo: Binäre Suche

Video abspielenBeim Abspielen wird das Video von YouTube geladen. Dabei werden Daten (u. a. Ihre IP-Adresse) an Google übertragen. Datenschutzerklärung

Arbeitsblatt: Binäre Suche

Arbeitsblatt »Binäre Suche« (PDF)