Wir schreiben eine Funktion namens binary_search(li, el). Die Funktion nimmt eine sortierte Liste li und ein gesuchtes Element el an. Wenn sie das Element in der Liste findet, gibt sie die Position (den Index) des Elements zurück. Wenn nicht, gibt sie None zurück.

Vor uns liegt eine sortierte Liste mit dem kleinsten Element ganz links und dem grössten Element ganz rechts. Bei der Binärsuche schauen wir uns jeweils das mittlere Element des Suchbereichs¹⁾ an und vergleichen es mit dem gesuchten Element. Es ergeben sich drei Möglichkeiten:

1. Das mittlere Element entspricht dem gesuchten Element. Also geben wir den Index des mittleren Elements zurück und sind fertig.
2. Das mittlere Element ist grösser als das gesuchte Element. Also schränken wir den Suchbereich ein, sodass alles ab der Mitte rechts nicht weiter betrachtet wird.
3. Das mittlere Element ist kleiner als das gesuchte Element. Also müssen wir nur noch in dem Bereich suchen, der rechts der Mitte liegt.

Bei 2. und 3. wird der Suchbereich halbiert und es ergibt sich daraus eine neue Mitteposition. Das Element an dieser Position verleichen wir erneut mit dem gesuchten Element. Wir wiederholen diese Schritte solange, bis:

• das Element gefunden wurde oder
• der Suchbereich nicht mehr kleiner werden kann. In diesem Fall haben wir das Element nicht gefunden. Also geben wir None zurück.

Wir programmieren also einen Algorithnus, bei dem eindeutige Schrite immer wieder durchgeführt werden – solange, bis die Arbeit erledigt ist. Wie bei den meisten Algorithmen sind hierzu zuerst ein paar einmalige Schritte nötig. Dann kommt eine Schleife, in der die Schritte stehen, die wiederholt werden sollen.

Nachdem wir den Funktionskopf hingeschrieben haben, legen wir die beiden Variablen left und right fest, mit denen wir den Suchbereich abstecken. Zu Beginn ist left 0 und right so gross wie der grösste Index der Liste.

Python

def binary_search(li,el):
    left = 0
    right = len(li)-1

Wir müssen so lange suchen, wie wir den Suchbereich noch verkleinern können.

jhtfjhfjhgfj ++ Python

def binary_search(li,el):
    left = 0
    right = len(li)-1

+

In dieser sortierten Liste mit 16 Zahlen wird nach der Zahl 42 gesucht. Der Suchbereich wird duch die Variablen l und r (für links und rechts) begrenzt. Zu Beginn erstreckt sich der Suchbereich über die gesamte Liste: l ist 0 und r ist so gross wie der höchste Index der Liste: len(li)-1.