Suchstrategie: Binäre Suche

Als eines der schnellsten Suchalgorithmen gilt der Binary Search. Aus einer sortierten Datensammlung ordinal (Grössenordnung) unterscheidbaren Werte benötigt der Algorithmus höchstens die Hälfte der Anzahl Datensätze an Schritte, um sicherzustellen, ob ein gewisser Wert darin liegt oder nicht.

Wegen der hohen Geschwindigkeit dieses Verfahrens greifen viele Betriebssysteme, die ein Indexierungsschema zunutze nehmen, nach diesem Algorithmus.

Wie funktioniert er wohl? Ganz einfach. Ausgehend von einer sortierten Datenmenge aus Zahlen und einem Zielwert bestimmt es zuerst den mittleren Eintrag. Dieser ist nicht mit dem Median zu verwechseln, hier wird eben bei einer geraden Anzahl Datensätze der tiefere der Mittleren 2 als Bezugswert bezogen. Gleicht dieser Wert dem Zielwert, so terminiert es erfolgreich. Ist der Wert jedoch kleiner als der Gesuchte, so wiederholt es den Vorgang mit der grösseren Hälfte. Stimmt das Gegenteil zu (Mittlerer Wert > Zielwert), dann wird stattdessen mit der tieferen Hälfte fortgefahren. Der Prozess hört nicht auf bis der Wert aufgefunden worden ist oder alle Einträge der Suchliste abgedeckt worden sind.

In Stichworte zusammengefasst:

Ausgangslage
- Eine sortierte Werteliste
- Ein Zielwert

Ansatz

1. Bestimme den Wert im Zentrum (linke bei einer geraden Anzahl Einträge)
2. Vergleiche den Zentralwert mit dem Zielwert:
   a. Zentralwert > Zielwert -> Hälfte mit den grösseren Werten ausschliessen
   b. Zentralwert == Zielwert -> Erfolgreich terminieren
   c. Zentralwert Hälfte mit den kleineren Werten ausschliessen
3. Falls der Zielwert nicht gefunden wurde und im Suchraum mind. 1 Wert noch besteht -> Schritt 2 wiederholen

Im Gegensatz zum Klischee in der Programmierwelt "leichter gesagt als getan", ist die Übertragung des Konzepts zu (Python) Code kinderleicht.

def binary_search(target_value: int, entries: list):
    num_entries = len(entries)
    if num_entries == 0:
        return False
    if num_entries == 1:
        return entries[0] == target_value
    index_center = num_entries // 2
    median = entries[index_center]
    if target_value == median:
        return True
    elif target_value > median:
        return binary_search(target_value, entries[index_center:])
    elif target_value < median:
        return binary_search(target_value, entries[:index_center])
    return False