Rasantes Suchen in Listen: Die binäre Suche

Teil 1 einer Serie über performantes Programmieren mit Bezug auf Operations Research.

TL;DR

Binäre Suche ist signifikant schneller als stumpfes Suchen in Listen. Sie setzt voraus, dass die Elemente in der Liste nach einer fixen Logik sortiert sind. Sie sollte dann eingesetzt werden, wenn die betroffene Liste explizit Duplikate des selben Elements enthalten kann und nicht z.B. die Anfügereihenfolge relevant ist. Kann bzw. soll jeder Wert nur einmalig in der Liste vorkommen, ist eher das HashSet zu empfehlen.

Ausgangslage

In vielen Situationen müssen wir prüfen, ob sich ein Element in einer Liste befindet. Die simpelste Methode, leider auch die am wenigsten performante Methode, um dies zu tun, ist der Befehl liste.contains(). Leider ist diese Methode nicht wirklich performant und es empfiehlt sich - da wo es möglich ist - auf Alternativen auszuweichen. Die binäre Suche erlaubt es den Suchaufwand drastisch zu reduzieren, setzt aber eine sortiere Liste voraus.

Implikation von list.contains()

Die Prüfung liste.contains() iteriert im Hintergrund stumpft über alle Elemente in der Liste und prüft, ob diese dem gesuchten Wert entsprechen. Ab dem ersten Treffer, gibt die Funktion das Resultat true zurück.

import random
liste = list(range(10000)) # = [0,1,2,...,9999]

# Entfernt 100 zufällige Zahlen aus der Liste
removals = random.sample(liste, 100)
for i in removals:
    liste.remove(i)

# Prüfung ob die Liste die Zahl 9800 noch enthält
if liste.contains(9800):
    print("Die Zahl ist enthalten")

Im zu vor dargestellten Fall benötigen wir lediglich eine Zeile Code, um zu prüfen, ob 9800 noch in der Liste enthalten sind. Zwar klingt es verlockend, diese vorimplementierte Methode zu verwenden, der Preis sollte jedoch nicht unterschätzt werden. Immer wenn liste.contains() aufgerufen wird, wird im Hintergrund die folgende Prüfung durchgeführt.

for i in liste:
    if i == 9800:
        return True

In dem oben dargestellten Fall, müssen also im schlimmsten Fall alle 9900 verbleibenden Elemente (beginnend bei 0) geprüft werden. Dies trifft dann zu, wenn die Zahl 9800 nicht mehr in der Liste ist. Im besten Fall werden 9701 Elemente geprüft, nämlich dann wenn alle 100 entfernten Elemente kleiner als 9800 sind. Wenn wir eine solche Prüfung einmal durchführen, ist die benötigte Rechenzeit vermutlich unkritisch. In einem zeitsensitiven Optimierungsalgorithmus hingehen kann die Prüfung die Laufzeit spürbar negativ beeinflussen.

In dem hier vorliegenden Fall können wir jedoch eine Eigenschaft der Liste nutzen, die den Prüfaufwand stark reduzieren wird: die Liste ist (aufsteigend) sortiert.

Binäre Suche

TL;DR

Sei n die Anzahl Elemente in einer Liste (oben: n=9900): Mit binärer Suche sinkt der maximale Prüfaufwand von n auf log₂(n), d.h. auf einen Bruchteil des ursprünglichen Aufwands. Für das o.g. Beispiel sinkt der Aufwand auf maximal 13. Dafür muss die Liste aber gemäß irgendeiner Metrik sortiert sein.

Erläuterung

Diese Suchmethode funktioniert nur bei sortierten Listen. Hierbei ist es unerheblich, ob die Listen nach Zahlen (auf- oder absteigend) sortiert sind, oder einer selbst definierten lexikographischen Sortierung folgen. Eine lexikographische Sortierung ist beispielsweise der Medaillenspiegel bei den olympischen Spielen: eine Goldmedaille ist immer besser als eine beliebige Anzahl Silbermedaillen, eine Silbermedaille ist immer besser als eine beliebige Anzahl Bronzemedaille. Eine zwei Goldmedaillen sind besser als Eine usw.

Die Idee hierbei ist, dass wir in einer sortierten Liste das Suchintervall, in dem sich der Suchwert befinden müsste, schrittweise eingrenzen können. In jeder Iteration des Verfahrens wird der Wert in der Mitte des aktuellen Suchintervalls (das sich schrittweise verkleinert) betrachtet.

Ist dieser Wert

• kleiner als unser Suchwert, können wir ableiten, dass sich der Suchwert rechts davon befinden muss.
• größer als der Suchwert, wissen wir, dass sich der Suchwert links von der soeben ermittelten Mitte befindet.

Vorgehen

Wir passen dann die untere- (Wert in der Mitte < Suchwert) bzw. obere (Wert in der Mitte > Suchwert) Grenze des Suchintervalls an und führen anschließend eine weitere Iteration durch. Für den Fall, dass der Wert in der Mitte des Intervalls genau unserem Suchwert entspricht stoppt das Verfahren. Entspricht die linke Seite des Suchintervalls der rechten Seite, wissen wir, dass der Suchwert nicht enthalten ist.

Algorithmus

funktion binäre_suche(liste, suchwert):
    # Gibt den Index des Suchwerts in der Liste zurück. Ist dieser
    # nicht enthalten, wird -1 zurück gegeben
    index = -1
    links = 0 # erster Wert in der Liste
    rechts = len(liste)-1 # letzter Wert in der Liste

    solange links <= rechts:
        mitte = aufrunden((rechts+links)/2)
        wenn liste[mitte] == suchwert:
            return mitte

        wenn liste[mitte] < suchwert:
            # Die Mitte des Betrachungsintervalls ist kleiner als der Suchwert
            links = mitte + 1
        sonst:
            # Die Mitte des Betrachungsintervalls ist größer als der Suchwert
            rechts = mitte - 1

    return index

Beispiel

Wir betrachten die folgende sortierte Liste mit 20 Elementen und wollen in ihr die Zahl 13 suchen.

liste = [2,2,2,3,3,4,5,6,6,6,7,8,9,9,9,10,13,18,19,20]

Nachfolgend wird das Verfahren angewandt. Hierbei gilt das Farbschema links, mitte, rechts

Binäre Suche in Python

Python hat bereits alle Hilfsmittel an Bord, um die binäre Suche auszuführen. Es ist lediglich ein kleiner Wrapper um die bisect Funktion notwendig:

from bisect import bisect_left

def bs_contains(liste, suchwert):
    """
        Gibt True zurück, wenn der Suchwert enthalten ist, False andernfalls.
    """
    # pos = Position in der Liste an die der Suchwert insertiert werden müsste 
    # bzw. Position des Suchwerts, sofern er enthalten ist.
    pos = bisect_left(liste, suchwert)
    if pos >= len(liste):
        # Suchwert ist nicht enthalten und müsste hinten angefügt werden
        return False
    if liste[pos] != suchwert:
        # Wert an Zielposition ist nicht der Suchwert
        # --> Suchwert ist nicht enthalten
        return False
    
    return True

Hierbei implementiert die Funktion bisect_left die binäre Suche und gibt die Position zurück, die der Suchwert haben müsste, ob er sich nun in der Liste befindet oder nicht. Entspricht das Element an der gefundenen Position dem Suchwert, ist dieser in der Liste, sonst nicht.

Einfach immer sortieren?

Abschließend ist es wichtig, nicht auf die Idee zu kommen eine Liste immer zu sortieren, bevor ein Element darin gesucht oder nachdem ein Element (stumpf) hinzugefügt wird. Stattdessen lohnt es sich, darauf zu achten, die Liste im Ablauf des Programms sortiert zu lassen.

Man könnte beispielsweise auf die Idee kommen eine Liste mit Nachbarlösungen oder eine Liste mit Knoten in einem Suchbaum wie folgt mit neuen Lösungen bzw. Knoten zu bestücken:

• Füge das Element hinten an die Liste an
• Sortiere die Liste (Komplexität: O(n log n))

In diesem Falle, wird für jedes neue Element eine Sortierprozedur mit n log n Schritten angestoßen. Dies frisst zu viele Ressourcen. Idealerweise fügt man Elemente bereits mit Hilfe der binären Suche hinzu indem zuerst die potentielle Position mit bisect_left gesucht wird und anschließend an der gefundenen Stelle eingefügt wird. Eine Funktion, die beides in einem erledigt ist insort_left.