Halbiere den Suchraum bei jedem Schritt. O(log n) statt O(n): bei einer Milliarde Einträgen reichen 30 Vergleiche. Voraussetzung: sortiertes Array.
Binäre Suche halbiert bei jedem Schritt den Suchraum, indem sie das mittlere Element prüft und entscheidet ob der Suchwert davor oder danach liegt. Funktioniert nur auf sortierten Arrays. Komplexität: O(log n).
Was du in der Klausur können musst:
In Klausuren oft gefragt: trace die Suche Schritt für Schritt für ein gegebenes Array und einen Suchwert. Schreibe pro Iteration die aktuellen low/high/mid-Indizes auf, das ist die Standard-Aufgabenform.
Stell dir vor, du suchst eine Seite in einem Wörterbuch:
Du schlägst nicht Seite 1 auf und blätterst durch. Du schlägst in der Mitte auf, schaust ob das gesuchte Wort davor oder dahinter steht, und wiederholst das Halbieren.
Das ist binäre Suche. Bei jeder Halbierung verringert sich die Suchmenge um 50%, daher die Komplexität .
Binäre Suche funktioniert nur auf sortierten Arrays. Ist das Array unsortiert, musst du es erst sortieren (kostet ), oder linear suchen.
public static int binarySearch(int[] arr, int target) {
int lo = 0;
int hi = arr.length - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (arr[mid] == target) return mid;
if (arr[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return -1;
}Bei jeder Iteration halbiert sich der Suchraum:
Wie oft kann man halbieren bis man bei 1 ankommt? Mal.
| n | Maximale Vergleiche (log₂ n) |
|---|---|
| 16 | 4 |
| 1.024 | 10 |
| 1.000.000 | 20 |
| 1 Mrd. | 30 |
Bei einer Milliarde Einträgen reichen 30 Vergleiche, das ist die Magie von .
Java hat Arrays.binarySearch() und Collections.binarySearch() direkt eingebaut. Python's bisect Modul bietet das gleiche.
Alle Tabs der Lerneinheit (Erklärung · Interaktiv · Quiz) als durchgehender Text. Ideal zum Wiederholen vor der Klausur — und für Suchmaschinen wie Google, Bing und KI-Suche (ChatGPT, Perplexity).
Binäre Suche halbiert bei jedem Schritt den Suchraum, indem sie das mittlere Element prüft und entscheidet ob der Suchwert davor oder danach liegt. Funktioniert nur auf sortierten Arrays. Komplexität: O(log n).
Wie wächst der Aufwand eines Algorithmus mit der Eingabe-Größe? Konstant, linear, quadratisch, und wann macht der Unterschied wirklich was aus?
Der intuitive Sortieralgorithmus: zwei verschachtelte Schleifen, größere Werte blubbern nach oben. Einfach zu erklären, in der Praxis aber zu langsam: O(n²).
Der schnellste der Klassiker im Average Case: O(n log n), in-place, partitioniert um einen Pivot. Bei sortiertem Input rutscht er aber auf O(n²) ab.
Was du in der Klausur können musst:
In Klausuren oft gefragt: trace die Suche Schritt für Schritt für ein gegebenes Array und einen Suchwert. Schreibe pro Iteration die aktuellen low/high/mid-Indizes auf, das ist die Standard-Aufgabenform.
Stell dir vor, du suchst eine Seite in einem Wörterbuch:
Du schlägst nicht Seite 1 auf und blätterst durch. Du schlägst in der Mitte auf, schaust ob das gesuchte Wort davor oder dahinter steht, und wiederholst das Halbieren.
Das ist binäre Suche. Bei jeder Halbierung verringert sich die Suchmenge um 50%, daher die Komplexität O(log n).
Binäre Suche funktioniert nur auf sortierten Arrays. Ist das Array unsortiert, musst du es erst sortieren (kostet O(n log n)), oder linear suchen.
public static int binarySearch(int[] arr, int target) {
int lo = 0;
int hi = arr.length - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (arr[mid] == target) return mid;
if (arr[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return -1;
}Java: lo/hi markieren den aktuellen Suchbereich. mid wird halbiert berechnet (lo + (hi-lo)/2 statt (lo+hi)/2 zur Vermeidung von Integer-Overflow).
def binary_search(arr, target):
lo, hi = 0, len(arr) - 1
while lo <= hi:
mid = (lo + hi) // 2
if arr[mid] == target:
return mid
if arr[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1Python: identische Logik. Integer-Overflow ist bei Python kein Problem, daher genügt (lo+hi)//2.
Bei jeder Iteration halbiert sich der Suchraum:
n → n/2 → n/4 → n/8 → dots → 1
Wie oft kann man n halbieren bis man bei 1 ankommt? log₂ n Mal.
| n | Maximale Vergleiche (log₂ n) |
|---|---|
| 16 | 4 |
| 1.024 | 10 |
| 1.000.000 | 20 |
| 1 Mrd. | 30 |
Bei einer Milliarde Einträgen reichen 30 Vergleiche, das ist die Magie von O(log n).
Java hat Arrays.binarySearch() und Collections.binarySearch() direkt eingebaut. Python's bisect Modul bietet das gleiche.
Beobachte wie sich der Suchbereich halbiert. Der orange Highlight markiert das aktuelle Mittelpunkt-Element. Werte außerhalb des Suchbereichs werden ausgegraut.
Probier folgendes:
Halt fest: jede Verdopplung der Eingabe kostet nur einen zusätzlichen Vergleich.
Interaktive Visualisierung
Vergleicht lineare und binäre Suche mit Schritt-Counter pro Algorithmus.
Faustregel zum Mitnehmen: Binäre Suche skaliert logarithmisch. Bei 1 Million Einträgen reichen ~20 Vergleiche, bei 1 Milliarde ~30. Linear bräuchte 1 Million bzw. 1 Milliarde.
Klausurfragen mit Lösungen (6)
Antwort: O(log n)
Erklärung: Bei jeder Iteration halbiert sich der Suchraum: n → n/2 → n/4 → ... → 1. Das ist exakt die Definition von O(log n).
Antwort: Das Array muss sortiert sein
Erklärung: Binäre Suche funktioniert nur auf sortierten Arrays. Sonst kann man nicht entscheiden, ob das Target links oder rechts vom Pivot liegt.
Antwort: Etwa 20
Erklärung: log₂(1.000.000) ≈ 20. Genau das ist die Magie: bei 1 Million Einträgen reichen 20 Vergleiche, bei 1 Milliarde nur 30.
// Variante A:
int mid = (lo + hi) / 2;
// Variante B:
int mid = lo + (hi - lo) / 2;Antwort: Variante B
Erklärung: In Java kann (lo+hi) bei sehr großen Indizes über Integer.MAX_VALUE laufen. lo + (hi-lo)/2 ist mathematisch äquivalent, vermeidet aber den Overflow. In Python irrelevant, da Python Integer beliebig groß werden können.
Antwort: Nein, sortieren kostet O(n log n), das ist langsamer als ein einzelner linearer Scan
Erklärung: Sortieren kostet O(n log n), eine lineare Suche kostet nur O(n). Bei einer einzigen Suche lohnt sich der Sortier-Aufwand nicht. Bei vielen Suchen auf demselben Array sieht es anders aus: einmal sortieren, dann beliebig oft binär suchen.
Antwort: 10
Erklärung: log₂(1024) = 10. Bei jeder Iteration halbiert sich der Suchraum, also genau 10 Halbierungen bis 1 Element übrig bleibt. Verallgemeinert: ⌈log₂(n+1)⌉ Vergleiche im Worst Case.
Typ: Zahlen-Eingabe