Neueste Populär Trending
Suchalgorithmen: Binäre Suche in Python

» Suchalgorithmen: Binäre Suche (binary search)

Im letzten Beitrag » Suchalgorithmen: Min-/Max-Suche und Lineare Suche (Linear Search) haben wir zwei sehr einfache Algorithmen mit linearer Laufzeit von O(n)=n kennengelernt. Die binäre Suche hingegen ist ein Algorithmus, welcher im Worst-Case Szenario eine Laufzeit von O(n)=log₂(n) und im Best-Case Szenario eine Laufzeit von O(n)=1 hat, da der gesuchte Schlüssel sofort gefunden wird. Die binäre Suche ist daher das Standardverfahren für Suchprobleme.

Die Voraussetzung dafür ist, dass die Folge aufsteigend sortiert (geordnet) ist, d.h. wir haben A₀ ≤ A₁ ≤ … ≤ Aₙ₋₁ (Beispiel: suche nach einem Namen im Telefonbuch). Die binäre Suche nutzt Intervallhalbierung, d.h. das "Teile und Herrsche"-Prinzip (Divide & Conquer). Beispiel: Schlage das Telefonbuch in der Mitte auf, vergleiche den gesuchten Namen mit einem Namen auf der Seite und entscheide, in welcher Hälfte des Telefonbuches sich der gesuchte Name befindet. Wiederhole das Verfahren nun mit dieser Hälfte solange, bis die richtige Seite gefunden ist.

Binäre Suche Beispiel

Binäre Suche Beispiel

Implementierung

Suche in einer sortierten Liste A nach einem Schlüssel key:

  • Beende die Suche erfolglos wenn die Liste leer ist
  • Nimm das Element auf der mittleren Position middle der Liste und Vergleiche es mit dem Schlüssel
    • Falls der Schlüssel key kleiner ist als das Element A[middle]: Durchsuche die linke Seite der Liste bis zum Element A[middle]
    • Falls der Schlüssel key größer ist als das Element A[middle]: Durchsuche die rechte Seite der Liste vom Element A[middle] bis zum Ende
    • Beende die Suche wenn der Schlüssel key gleich A[middle] ist

› Binäre Suche rekursiv implementieren

def binary_search_start(A, key):
    """Binäre Suche mit Rekursion.

    Startet die Rekursion.

    Args:
        A (list): Menge A
        key (object): Element das gefunden werden soll.

    Returns:
        Index i, sodass 0 <= i < len(A) und A[i] == key, oder -1 falls key nicht auftritt.
    """
    if len(A) == 0:
        # key wurde nicht gefunden, da liste leer
        return -1
    if len(A) == 1:
        # liste hat nur 1 Element, Rekursion nicht nötig, da entweder im Index 0 vorhanden oder nicht.
        if A[0] == key:
            return 0
        else:
            return -1

    # Starte Rekursion
    return binary_search_work(A, key, 0, len(A)-1)

def binary_search_work(A, key, left, right):
    """Binäre Suche mit Rekursion.

    Args:
        A (list): Menge A
        key (object): Element das gefunden werden soll.
        left (int): Linke Grenze der Menge.
        right (int): Rechte Grenze der Liste.

    Returns:
        Index i, sodass 0 <= i < len(A) und A[i] == key, oder -1 falls key nicht auftritt.
    """
    if right < left:
        # key wurde nicht gefunden
        return -1

    middle = int((left + right) / 2)
    if key < A[middle]:
        # key vermutlich in der linken seite -> anpassen der rechten grenze
        return binary_search_work(A, key, left, middle-1)
    if key > A[middle]:
        # key vermutlich in der rechten seite -> anpassen der linken grenze
        return binary_search_work(A, key, middle+1, right)

    # key wurde gefunden
    return middle

if __name__ == '__main__':
    data = [12, 17, 23, 24, 31, 32, 36, 37, 42, 47, 53, 55, 64, 75, 89, 91, 91, 93, 96]
    print('Binäre Suche mit Rekursion:', binary_search_start(data, 32))

› Binäre Suche iterativ implementieren

def binary_search(A, key):
    """Binäre Suche ohne Rekursion.

    Suche das Element key in der Menge A und gebe den Index des gefundenen Elements zurück.

    Args:
        A (list): Menge A
        key (object): Element das gefunden werden soll.

    Returns:
        int: Index i, sodass 0 <= i < len(A) und A[i] == key, oder -1 falls key nicht auftritt.
    """
    # Grenzen bestimmen
    left = 0
    right = len(A) - 1

    while left <= right:
        middle = int((left + right) / 2)  # Mitte der Liste (abgerundet)

        if key < A[middle]:
            # key vermutlich in der linken seite -> anpassen der rechten grenze
            right = middle - 1
        elif key > A[middle]:
            # key vermutlich in der rechten seite -> anpassen der linken grenze
            left = middle + 1
        else:
            # key wurde gefunden
            return middle

    # key wurde nicht gefunden
    return -1

if __name__ == '__main__':
    data = [12, 17, 23, 24, 31, 32, 36, 37, 42, 47, 53, 55, 64, 75, 89, 91, 91, 93, 96]
    print('Binäre Suche ohne Rekursion:', binary_search(data, 32))

Vergleich mit linearer Suche

Bei großen Datenmengen ist die binäre Suche aufgrund der logarithmischen Laufzeit wesentlich effizienter als die lineare Suche, da nur log₂(n) Elementaroperationen benötigt werden. Bei einer Verdoppelung der Datenmenge bedeutet dies, dass die lineare Suche den doppelten Zeitaufwand benötigt, wohingegen die binäre Suche nur einen Vergleich mehr braucht.

Verfahren / #Elemente 10 10^2 10^3 10^4
Lineare Suche (n) 10 10^2 10^3 10^4
Binäre Suche (log n) ≈3.3 ≈6.6 ≈9.9 ≈13.3

Literatur

Kommentar hinzufügen

Wir verwenden Cookies um Inhalte zu personalisieren und unsere Besucherstatistik zu führen. Bitte entscheiden Sie sich, ob Sie unsere Cookies akzeptieren möchten.