🏠 Startseite

Binäre Suche & Komplexität

Effizient suchen und Algorithmen bewerten

Vorlesung 12 | Fortgeschrittene Algorithmen

Von O(n) zu O(log n) - ein gewaltiger Unterschied!

Lernziele

  • Binäre Suche verstehen und implementieren
  • Lineare vs. binäre Suche vergleichen
  • Die O-Notation (Big-O) verstehen
  • Zeitkomplexität von Algorithmen analysieren
  • Verschiedene Komplexitätsklassen kennen
  • Die richtige Datenstruktur/Algorithmus wählen

Wiederholung: Lineare Suche

int lineareSuche(int arr[], int n, int gesucht) { for (int i = 0; i < n; i++) { if (arr[i] == gesucht) { return i; } } return -1; // nicht gefunden }

Eigenschaften

  • Best Case: 1 Vergleich
  • Worst Case: n Vergleiche
  • Average: n/2 Vergleiche

Problem: Bei 1 Million Elementen → bis zu 1 Million Vergleiche!

Kann es schneller gehen?

Das Telefonbuch-Beispiel

Suche nach "Müller" im Telefonbuch mit 500.000 Namen:

Linear (von vorne)

Starten bei "A"...

Blättern... Blättern... Blättern...

Bis zu 500.000 Namen prüfen!

Intelligent (in der Mitte)

Öffne in der Mitte → "L"

"Müller" > "L" → rechte Hälfte

Öffne Mitte der rechten Hälfte...

Nur ~19 Schritte!

Binäre Suche - Die Idee

Voraussetzung: Array muss sortiert sein!

  1. Schaue das mittlere Element an
  2. Wenn es der gesuchte Wert ist → gefunden!
  3. Wenn der gesuchte Wert kleiner ist → suche in linker Hälfte
  4. Wenn der gesuchte Wert größer ist → suche in rechter Hälfte
  5. Wiederhole, bis gefunden oder keine Elemente mehr übrig

Divide and Conquer: In jedem Schritt halbieren wir den Suchbereich!

Binäre Suche - Der Algorithmus

Variablen

  • links = linke Grenze (anfangs 0)
  • rechts = rechte Grenze (anfangs n-1)
  • mitte = mittlerer Index

Die Formel für Mitte:

mitte = links + (rechts - links) / 2

Ablauf

  1. Berechne mitte mit der Formel
  2. Vergleiche arr[mitte] mit gesuchtem Wert
  3. Wenn gleich → gefunden!
  4. Wenn gesucht < arr[mitte]:
    rechts = mitte - 1
  5. Wenn gesucht > arr[mitte]:
    links = mitte + 1
  6. Wiederhole Schritte 1-5 solange links <= rechts
    (= solange es noch Elemente zum Durchsuchen gibt)

Abbruch: Wenn links > rechts → Element nicht gefunden! (Suchbereich ist leer)

Binäre Suche: Suche nach 23

Schritt 1: links=0, rechts=8 → mitte = 0 + (8-0)/2 = 4, arr[4] = 17

03
17
211
315
417
523
631
742
855

23 > 17 → rechte Hälfte

Schritt 2: links=5, rechts=8 → mitte = 5 + (8-5)/2 = 6, arr[6] = 31

3
7
11
15
17
523
631
742
855

23 < 31 → linke Hälfte

Binäre Suche: Suche nach 23 (Fortsetzung)

Schritt 3: links=5, rechts=5 → mitte = 5 + (5-5)/2 = 5, arr[5] = 23

3
7
11
15
17
523
31
42
55

23 == 23 → Gefunden an Index 5!

Nur 3 Schritte statt bis zu 9 bei linearer Suche!

Binäre Suche - Der Code

int binaereSuche(int arr[], int n, int gesucht) { int links = 0; int rechts = n - 1; while (links <= rechts) { int mitte = links + (rechts - links) / 2; if (arr[mitte] == gesucht) { return mitte; // Gefunden! } else if (arr[mitte] < gesucht) { links = mitte + 1; // Rechte Hälfte } else { rechts = mitte - 1; // Linke Hälfte } } return -1; // Nicht gefunden }

Warum links + (rechts - links) / 2?

Naiv: (links + rechts) / 2

Problem: Overflow bei großen Arrays!

Wenn links = 2 Milliarden und rechts = 2 Milliarden:

links + rechts = 4 Milliarden → Overflow!

int kann nur bis ~2.1 Milliarden

Sicher: links + (rechts - links) / 2

Mathematisch identisch, aber:

(rechts - links) ist immer ≤ n

Kein Overflow möglich!

Immer diese Variante verwenden!

Sichere Mitte: Schritt für Schritt

Formel: links + (rechts - links) / 2

Beispiel: links = 0, rechts = 8

1. rechts - links = 8 - 0 = 8

2. (rechts - links) / 2 = 8 / 2 = 4

3. links + 4 = 0 + 4 = 4

→ mitte = 4 ✓

Die Idee dahinter

0
1
2
3
4
5
6
7
8

|←──────────────── Distanz: 8 ────────────────→|

|←────── halbe Distanz: 4 ──────→|

Startpunkt + halbe Distanz = Mitte

Warum sicher? (rechts - links) ist immer kleiner als (rechts + links), daher kein Overflow!

Wie viele Schritte braucht binäre Suche?

Die Frage: Wie oft kann man n halbieren, bis nur noch 1 Element übrig ist?

Beispiel: n = 8

8 Elemente

↓ ÷ 2 (Schritt 1)

4 Elemente

↓ ÷ 2 (Schritt 2)

2 Elemente

↓ ÷ 2 (Schritt 3)

1 Element ✓

3 Halbierungen → 3 Schritte

Beispiel: n = 16

16 → 8 → 4 → 2 → 1

4 Halbierungen → 4 Schritte

Beispiel: n = 1024

1024 → 512 → 256 → 128 → 64 → 32 → 16 → 8 → 4 → 2 → 1

10 Halbierungen → 10 Schritte

Formel: Anzahl Schritte = log₂(n)

log₂(8) = 3, weil 2³ = 8   |   log₂(16) = 4, weil 2⁴ = 16   |   log₂(1024) = 10, weil 2¹⁰ = 1024

Die O-Notation (Big-O)

Was beschreibt sie?

Die O-Notation beschreibt, wie die Laufzeit eines Algorithmus mit der Eingabegröße n wächst.

Was sie NICHT sagt:

  • Exakte Laufzeit in Sekunden
  • Konstante Faktoren
  • Performance auf bestimmter Hardware

Was sie SAGT:

  • Wie sich die Laufzeit skaliert
  • Wachstumsverhalten bei großem n
  • Algorithmen vergleichen

Die wichtigsten Komplexitätsklassen

O(1)

Konstant - Array-Zugriff, Variable lesen

O(log n)

Logarithmisch - Binäre Suche

O(n)

Linear - Lineare Suche, Array durchlaufen

O(n²)

Quadratisch - Bubble Sort, Selection Sort

O(2ⁿ)

Exponentiell - Naive Fibonacci, Brute Force

Konkrete Zahlen: n = 1.000.000

Komplexität Operationen Bei 1 Op/μs
O(1) 1 1 μs
O(log n) 20 20 μs
O(n) 1.000.000 1 Sekunde
O(n²) 10¹² 11,5 Tage
O(2ⁿ) 10³⁰⁰⁰⁰⁰ Länger als das Universum!

Komplexität visualisiert: Der Graph

Eingabegröße n Zeit / Operationen O(1) O(log n) O(n) O(n²) O(2ⁿ) 0 n 2n 3n 4n

Was zeigt der Graph?

  • ● O(1) bleibt flach
  • ● O(log n) wächst sehr langsam
  • ● O(n) wächst gleichmäßig
  • ● O(n²) explodiert schnell
  • ● O(2ⁿ) explodiert sofort!

Fazit: Je flacher die Kurve, desto besser der Algorithmus!

O(n) vs O(log n): Der große Unterschied

Lineare Suche vs. Binäre Suche

Array-Größe n Schritte O(n) O(log n)
n O(n) O(log n)
8 8 3
64 64 6
1.000 1.000 10
1.000.000 1.000.000 20

Bei 1 Million Elementen:

Linear: 1.000.000 Schritte

Binär: 20 Schritte

50.000× schneller!

Komplexität analysieren: Beispiele

O(1) - Konstant

int ersteElement(int arr[]) { return arr[0]; }

Immer 1 Operation, egal wie groß das Array

O(n) - Linear

int summe(int arr[], int n) { int s = 0; for(int i=0; i<n; i++) s += arr[i]; return s; }

n Durchläufe → n Operationen

Komplexität analysieren: Mehr Beispiele

O(n²) - Quadratisch

for(int i=0; i<n; i++) { for(int j=0; j<n; j++) { // Operation } }

n × n = n² Operationen

Verschachtelte Schleifen!

O(log n) - Logarithmisch

while (links <= rechts) { mitte = (links + rechts) / 2; if (arr[mitte] == gesucht) return mitte; // Halbieren... }

Suchbereich wird halbiert

Binäre Suche!

Regeln zur Komplexitätsanalyse

1. Konstanten ignorieren

O(3n) = O(n), O(100) = O(1)

2. Nur der größte Term zählt

O(n² + n + 1) = O(n²)

3. Verschachtelte Schleifen multiplizieren

for i... for j... → O(n × m)

4. Nacheinander addieren (dann größten nehmen)

O(n) + O(n²) = O(n²)

Quiz: Welche Komplexität?

for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { for (int k = 0; k < n; k++) { printf("Hallo"); } } }

Welche Komplexität hat dieser Code?

A) O(n)

B) O(n²)

C) O(n³)

D) O(3n)

Quiz Lösung

Antwort: C) O(n³)

Erklärung:

  • Äußere Schleife: n Durchläufe
  • Mittlere Schleife: n Durchläufe
  • Innere Schleife: n Durchläufe
  • Gesamt: n × n × n = n³

Achtung: Bei n=1000 sind das 1 Milliarde Operationen!

Lineare vs. Binäre Suche

Eigenschaft Lineare Suche Binäre Suche
Zeitkomplexität O(n) O(log n)
Voraussetzung Keine Array muss sortiert sein
Implementierung Sehr einfach Etwas komplexer
Bei 1 Mio. Elementen bis 1.000.000 Vergleiche max. 20 Vergleiche

Fazit: Wenn Sie oft suchen müssen, lohnt sich Sortieren + binäre Suche!

Einfach erklärt: Warum Sortieren wichtig ist

📚 Unsortiertes Bücherregal

Z
A
M
K
B

Buch "K" finden? → Jedes einzeln prüfen!

⏱️ Bis zu 5 Versuche

📖 Sortiertes Bücherregal

A
B
K
M
Z

Buch "K" finden? → Mitte prüfen, dann links/rechts!

⏱️ Nur 2-3 Versuche

💡 Merke: Einmal sortieren = viel schneller suchen!

Komplexitäten im Vergleich - Visualisiert

Wie viele Schritte bei n = 16 Elementen?

O(1) - Konstant

1

1 Schritt

Beispiel: arr[0] lesen

O(log n) - Logarithmisch

1
2
3
4

4 Schritte

Binäre Suche

O(n) - Linear

16 Schritte

Lineare Suche

O(n²) bei n=16? → 256 Schritte! 😱

Wann welchen Algorithmus?

✅ Lineare Suche

Verwende wenn:

  • Array ist unsortiert
  • Array ist klein (< 100)
  • Du nur einmal suchst

✅ Binäre Suche

Verwende wenn:

  • Array ist sortiert
  • Array ist groß
  • Du oft suchst

💡 Tipp

Sortieren + Binär:

  • Einmalig sortieren (Aufwand)
  • Jede Suche danach: O(log n)
  • Lohnt sich bei vielen Suchen!

🎯 Faustregel: Bei mehr als ~10 Suchen im gleichen Array → sortieren lohnt sich!

Häufige Fehler bei binärer Suche

❌ Fehler 1: Falsches Array

int arr[] = {5, 2, 8, 1, 9}; // unsortiert! binaereSuche(arr, 5, 8); // ❌ Falsch!

Lösung: Erst sortieren!

❌ Fehler 2: Off-by-One

// Falsch: while (links < rechts) // ❌ // Richtig: while (links <= rechts) // ✅

Merke: <= nicht vergessen!

❌ Fehler 3: Grenzen falsch

// Falsch: links = mitte; // ❌ Endlosschleife! // Richtig: links = mitte + 1; // ✅

✅ Tipp zum Testen

Teste immer mit:

  • Leeres Array
  • Ein Element
  • Element am Anfang/Ende
  • Element nicht vorhanden

Schritt-für-Schritt: Suche nach 7

Array: [2, 4, 7, 10, 15, 20] | Gesucht: 7

Schritt 1: links=0, rechts=5, mitte=(0+5)/2=2

02
14
27
310
415
520

arr[2] = 7 == 7? JA! Gefunden!

Nur 1 Schritt! Bei linearer Suche wären es 3 Schritte gewesen.

Praktische Anwendungen

📚 Wörterbuch

Wörter alphabetisch sortiert → Binäre Suche nach Wort

O(log n)

🎮 Highscore-Liste

Punkte sortiert → Schnell Position finden

O(log n)

🔍 Datenbanken

Indizes sind sortiert → Schnelle Suche nach ID

O(log n)

Schnelle Wiederholung

1. Was ist die Zeitkomplexität der binären Suche?

→ O(log n)

2. Was ist die wichtigste Voraussetzung?

→ Array muss sortiert sein!

3. Wie viele Vergleiche bei 1 Million Elementen?

→ Max. 20 Vergleiche (log₂(1.000.000) ≈ 20)

4. Was bedeutet O(n²)?

→ Verdoppelt sich n, vervierfacht sich die Zeit

Zusammenfassung

Binäre Suche

  • Nur für sortierte Arrays
  • Halbiert in jedem Schritt
  • O(log n) Komplexität
  • Extrem schnell bei großen Daten

O-Notation

  • Beschreibt Wachstumsverhalten
  • Wichtigste: O(1), O(log n), O(n), O(n²)
  • Konstanten werden ignoriert
  • Größter Term dominiert

Vielen Dank!

Das war die letzte Vorlesung!

🎉 Herzlichen Glückwunsch! 🎉

Sie haben jetzt alle wichtigen Konzepte der Fortgeschrittenen Programmierung gelernt!

Viel Erfolg bei der Prüfung! 💪

1 / 32