Overview
Binary Search halbiert einen sortierten Bereich, bis das target gefunden ist oder der Bereich leer ist.
Analogy
Wie im Wörterbuch suchen: Mitte aufschlagen, links oder rechts entscheiden, wiederholen.
Step-by-step
- Starte mit low = 0 und high = n - 1.
- Berechne mid = (low + high) // 2.
- Wenn arr[mid] == target, gib mid zurück.
- Wenn target kleiner ist, setze high = mid - 1.
- Sonst setze low = mid + 1, solange low <= high.
Visual
[1 3 5 7 9] -> Mitte 5 -> nach rechts -> 7 gefunden.
Common mistakes
- mid nach low/high-Update nicht neu berechnen.
- Schleife mit < statt <=, dadurch letztes Element übersprungen.
- mid = (low + high) kann überlaufen; besser low + (high - low) // 2.
Practice questions
- Trace für ein 7er-Array mit vorhandenem und fehlendem target.
- Variante mit Insertionsindex implementieren.
- Erklären, warum sortierte Daten Voraussetzung sind.