Binäre Suche

2.1 Definition der binären Suche und ihre Hauptkonzepte

Binäre Suche — ist ein Algorithmus zur Suche eines Elements in einem sortierten Array, der nach dem Prinzip der Halbierung des Arrays funktioniert. Dieser Algorithmus ist wesentlich effizienter als eine lineare Suche für große Arrays, da er die Anzahl der Überprüfungen durch Teilung des Arrays bei jeder Iteration reduziert.

Hauptkonzepte:

• Sortiertes Array: Die binäre Suche funktioniert nur bei sortierten Arrays.
• Halbierung: Der Algorithmus vergleicht das gesuchte Element mit dem Element in der Mitte des Arrays.
• Rekursive oder iterative Teilung: Wenn das gesuchte Element kleiner ist als das mittlere, geht die Suche im linken Teil des Arrays weiter, andernfalls im rechten.
• Abbruchbedingung: Die Suche wird beendet, wenn das Element gefunden wird oder der Suchbereich leer wird.

Wichtig! Für die binäre Suche wird ein sortiertes Array benötigt.

Damit die binäre Suche korrekt funktioniert, müssen die Eingabedaten aufsteigend sortiert sein. Dies ist die grundlegende und einzige Anforderung, da der Algorithmus darauf basiert, dass die Elemente des Arrays geordnet sind. Dadurch kann er effektiv die Hälfte der Elemente bei jedem Suchschritt ausschließen.

Beispiel eines sortierten Arrays:

sorted_array = [1, 3, 5, 7, 9, 11, 13]

2.2 Schrittweise Implementierung der binären Suche

Funktionsweise der binären Suche:

1. Initialisierung: Setze die anfänglichen Suchgrenzen (linke und rechte Grenze des Arrays).
2. Auswahl des mittleren Elements: Finde den Index des mittleren Elements des Arrays.
3. Vergleich: Vergleiche das mittlere Element mit dem gesuchten Wert.
4. Grenzen aktualisieren:
   1. Wenn das mittlere Element dem gesuchten Wert entspricht, gib seinen Index zurück.
   2. Wenn der gesuchte Wert kleiner ist als das mittlere Element, aktualisiere die rechte Suchgrenze.
   3. Wenn größer — aktualisiere die linke Grenze.
5. Wiederholung: Wiederhole die Schritte 2-4, bis das Element gefunden wird oder die linke Grenze größer als die rechte ist.

Schrittweiser Algorithmus:

1. Initialisierung: Setze left auf 0 und right auf len(arr) - 1.
2. Mittleres Element berechnen: mid = (left + right) // 2
3. Mit dem Ziel-Element vergleichen:
   1. Wenn arr[mid] == target, gib mid zurück.
   2. Wenn arr[mid] < target, aktualisiere left = mid + 1.
   3. Wenn arr[mid] > target, aktualisiere right = mid - 1.
4. Wiederholen: Zurück zu Schritt 2, solange left <= right.
5. Wenn das Element nicht gefunden wird: Gib -1 zurück.

Iterative Implementierung der binären Suche in Python:

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

# Beispiel der Verwendung:
sorted_array = [1, 3, 5, 7, 9, 11, 13]
target = 7
result = binary_search(sorted_array, target)
print(f"Element {target} gefunden an Index {result}")  # Ausgabe: Element 7 gefunden an Index 3

2.3 Zeitkomplexität der binären Suche O(log n)

Die binäre Suche hat eine Zeitkomplexität von O(log n), wobei n die Anzahl der Elemente im Array ist. Das bedeutet, dass der Algorithmus bei jedem Schritt die Menge der Elemente halbiert, was die Suche im Vergleich zur linearen Suche mit einer Zeitkomplexität von O(n) erheblich beschleunigt.

Analyse der Zeitkomplexität:

• Bester Fall (Best case): Element wird im ersten Schritt gefunden, O(1).
• Durchschnittlicher Fall (Average case): O(log n).
• Schlechtester Fall (Worst case): Element wird im letzten Schritt gefunden oder ist nicht vorhanden, O(log n).

Beispiel zur Analyse der Zeitkomplexität:

sorted_array = [1, 3, 5, 7, 9, 11, 13]
target = 7
index = binary_search(sorted_array, target)
print(f"Element {target} gefunden an Index {index}")  # Ausgabe: Element 7 gefunden an Index 3

# Der Algorithmus benötigte 3 Schritte (Logarithmus von 7 Elementen), um das Element zu finden,
# was O(log n) entspricht.

Grafische Darstellung der Komplexität:

Stell dir ein Array mit 16 Elementen vor.

Angenommen, wir suchen das Element 15, dann sind die Schritte wie folgt:

Erster Schritt. Prüft das mittlere Element (8 Elemente bleiben übrig).

Zweiter Schritt. Prüft das mittlere Element der verbleibenden Hälfte (4 Elemente bleiben übrig).

Dritter Schritt. Prüft das mittlere Element der verbleibenden Hälfte (2 Elemente bleiben übrig).

Vierter Schritt. Prüft das letzte Element (1 Element bleibt übrig).

Am Ende führt der Algorithmus 4 Schritte für ein Array mit 16 Elementen durch, was dem Logarithmus zur Basis 2 von 16 entspricht, also log2(16) = 4. Das ist die logarithmische Komplexität O(log n).