Binäre Suche
Zuletzt aktualisiert
Die binäre Suche findet einen Zielwert in einem **sortierten** Array, indem sie das Suchfenster wiederholt halbiert. Sie vergleicht das mittlere Element mit dem Ziel: Bei einem Treffer endet die Suche; andernfalls wird die Hälfte verworfen, die das Ziel nicht enthalten kann, und das Fenster schrumpft auf die andere Hälfte. Jeder Vergleich eliminiert die Hälfte der verbleibenden Elemente — deshalb läuft sie in O(log n): Die Suche in einer Million sortierter Werte braucht höchstens etwa 20 Vergleiche.
Die Animation oben zeigt die Zeiger lo, mid und hi und blendet nach jedem Vergleich die eliminierte Hälfte aus. Die eine unverhandelbare Voraussetzung: Das Array muss bereits sortiert sein — bei unsortierten Daten brauchst du die lineare Suche oder zuerst ein Sortierverfahren (siehe Merge Sort). Dieselbe Halbierungsidee steckt auch im binären Suchbaum.
Zeit- und Platzkomplexität
| Fall | Komplexität | Anmerkungen |
|---|---|---|
| Bester Fall | O(1) | Das mittlere Element ist beim ersten Vergleich das Ziel. |
| Durchschnittlicher Fall | O(log n) | Jeder Vergleich halbiert das verbleibende Fenster. |
| Schlechtester Fall | O(log n) | Das Fenster schrumpft auf ein einziges Element, bevor es zum Treffer oder Fehlschlag kommt. |
| Platz | O(1) | Die iterative Version hält nur die Indizes lo, hi und mid. |
Schritt für Schritt
| Schritt | Was passiert |
|---|---|
| 1 | Setze lo auf den ersten und hi auf den letzten Index des sortierten Arrays. |
| 2 | Berechne den mittleren Index: mid = (lo + hi) // 2. |
| 3 | Wenn a[mid] gleich dem Ziel ist, gib mid zurück — gefunden. |
| 4 | Wenn a[mid] **kleiner** als das Ziel ist, kann das Ziel nur in der rechten Hälfte liegen: setze lo = mid + 1. |
| 5 | Wenn a[mid] **größer** als das Ziel ist, durchsuche die linke Hälfte: setze hi = mid - 1. |
| 6 | Wiederhole ab Schritt 2, solange lo <= hi gilt; wird das Fenster leer, ist das Ziel nicht im Array. |
Durchgerechnetes Beispiel
Suche nach 5 in [1, 2, 3, 5, 7, 8, 9]:
| Durchlauf | Fenster (lo..hi) | mid | a[mid] | Aktion |
|---|---|---|---|---|
| 1 | [1, 2, 3, 5, 7, 8, 9] (0..6) | 3 | 5 | a[3] = 5 — Ziel bei Index 3 gefunden. |
Ein Fehlschlag, Schritt für Schritt
Die Suche nach 4 im selben Array zeigt, wie das Fenster leer wird:
| Durchlauf | Fenster (lo..hi) | mid | a[mid] | Aktion |
|---|---|---|---|---|
| 1 | 0..6 | 3 | 5 | 5 > 4 — durchsuche die linke Hälfte, hi = 2. |
| 2 | 0..2 | 1 | 2 | 2 < 4 — durchsuche die rechte Hälfte, lo = 2. |
| 3 | 2..2 | 2 | 3 | 3 < 4 — lo wird 3, das Fenster ist leer: nicht gefunden. |
Wann die binäre Suche verwenden
| Verwenden, wenn | Vermeiden, wenn |
|---|---|
| Die Daten bereits sortiert sind (oder du sie viele Male durchsuchst) | Die Daten unsortiert sind und nur einmal durchsucht werden — vorheriges Sortieren kostet O(n log n) |
| Die Sammlung schnellen wahlfreien Zugriff erlaubt (Arrays) | Du nur sequenziellen Zugriff hast (verkettete Listen) |
Der Datensatz groß ist — O(log n) glänzt bei großem Maßstab | Der Datensatz winzig ist — ein einfacher Durchlauf ist genauso schnell und simpler |
Binary Search-Code
Eine saubere, lauffähige Binary Search-Implementierung in Python, JavaScript, Java, C++, C, Pseudocode. Wähle eine Sprache, kopiere den Code oder öffne ihn vorgeladen im Coddy-Playground.
Binary Search-Code in Python
Python
1def binary_search(a, target):2 lo, hi = 0, len(a) - 13 while lo <= hi:4 mid = (lo + hi) // 25 if a[mid] == target:6 return mid7 if a[mid] < target:8 lo = mid + 1 # search the right half9 else:10 hi = mid - 1 # search the left half11 return -112
13
14nums = [1, 2, 3, 5, 7, 8, 9] # must be sorted15print("Index of 5:", binary_search(nums, 5))16print("Index of 4:", binary_search(nums, 4))Binary Search-Code in JavaScript
JavaScript
1function binarySearch(a, target) {2 let lo = 0;3 let hi = a.length - 1;4 while (lo <= hi) {5 const mid = Math.floor((lo + hi) / 2);6 if (a[mid] === target) return mid;7 if (a[mid] < target) {8 lo = mid + 1; // search the right half9 } else {10 hi = mid - 1; // search the left half11 }12 }13 return -1;14}15
16const nums = [1, 2, 3, 5, 7, 8, 9]; // must be sorted17console.log("Index of 5:", binarySearch(nums, 5));18console.log("Index of 4:", binarySearch(nums, 4));Binary Search-Code in Java
Java
1public class Main {2 static int binarySearch(int[] a, int target) {3 int lo = 0;4 int hi = a.length - 1;5 while (lo <= hi) {6 int mid = (lo + hi) / 2;7 if (a[mid] == target) return mid;8 if (a[mid] < target) {9 lo = mid + 1; // search the right half10 } else {11 hi = mid - 1; // search the left half12 }13 }14 return -1;15 }16
17 public static void main(String[] args) {18 int[] nums = {1, 2, 3, 5, 7, 8, 9}; // must be sorted19 System.out.println("Index of 5: " + binarySearch(nums, 5));20 System.out.println("Index of 4: " + binarySearch(nums, 4));21 }22}Binary Search-Code in C++
C++
1#include <iostream>2#include <vector>3
4int binarySearch(const std::vector<int>& a, int target) {5 int lo = 0;6 int hi = static_cast<int>(a.size()) - 1;7 while (lo <= hi) {8 int mid = lo + (hi - lo) / 2;9 if (a[mid] == target) return mid;10 if (a[mid] < target) {11 lo = mid + 1; // search the right half12 } else {13 hi = mid - 1; // search the left half14 }15 }16 return -1;17}18
19int main() {20 std::vector<int> nums = {1, 2, 3, 5, 7, 8, 9}; // must be sorted21 std::cout << "Index of 5: " << binarySearch(nums, 5) << "\n";22 std::cout << "Index of 4: " << binarySearch(nums, 4) << "\n";23 return 0;24}Binary Search-Code in C
C
1#include <stdio.h>2
3int binary_search(const int a[], int n, int target) {4 int lo = 0;5 int hi = n - 1;6 while (lo <= hi) {7 int mid = lo + (hi - lo) / 2;8 if (a[mid] == target) return mid;9 if (a[mid] < target) {10 lo = mid + 1; /* search the right half */11 } else {12 hi = mid - 1; /* search the left half */13 }14 }15 return -1;16}17
18int main(void) {19 int nums[] = {1, 2, 3, 5, 7, 8, 9}; /* must be sorted */20 int n = sizeof(nums) / sizeof(nums[0]);21 printf("Index of 5: %d\n", binary_search(nums, n, 5));22 printf("Index of 4: %d\n", binary_search(nums, n, 4));23 return 0;24}Binary Search-Code in Pseudocode
Pseudocode
1DECLARE nums : ARRAY[1:7] OF INTEGER2DECLARE n : INTEGER3n ← 74// The array must be sorted for binary search5nums[1] ← 16nums[2] ← 27nums[3] ← 38nums[4] ← 59nums[5] ← 710nums[6] ← 811nums[7] ← 912
13FUNCTION binarySearch(target : INTEGER) RETURNS INTEGER14 DECLARE lo : INTEGER15 DECLARE hi : INTEGER16 DECLARE mid : INTEGER17 lo ← 118 hi ← n19 WHILE lo <= hi DO20 mid ← (lo + hi) DIV 221 IF nums[mid] = target THEN22 RETURN mid23 ENDIF24 IF nums[mid] < target THEN25 // Target is larger — search the right half26 lo ← mid + 127 ELSE28 // Target is smaller — search the left half29 hi ← mid - 130 ENDIF31 ENDWHILE32 RETURN -133ENDFUNCTION34
35OUTPUT "Index of 5 is ", binarySearch(5)36OUTPUT "Index of 4 is ", binarySearch(4)FAQ zur binären Suche
Was ist die Zeitkomplexität der binären Suche?
O(log n) im durchschnittlichen und im schlechtesten Fall, weil jeder Vergleich das verbleibende Suchfenster halbiert, und O(1) im besten Fall, wenn das erste mittlere Element das Ziel ist. Die iterative Version benötigt O(1) zusätzlichen Platz.Warum braucht die binäre Suche ein sortiertes Array?
Der Halbierungsschritt beruht auf der Ordnung: Der Vergleich des Ziels mit dem mittleren Element verrät nur dann, welche Hälfte zu verwerfen ist, wenn alles links der Mitte kleiner und alles rechts davon größer ist. Bei unsortierten Daten ist dieser Schluss ungültig — nutze stattdessen die lineare Suche oder sortiere zuerst.
Was ist der Unterschied zwischen binärer Suche und linearer Suche?
Die lineare Suche prüft die Elemente eines nach dem anderen (
O(n)) und funktioniert mit jedem Array; die binäre Suche halbiert das Suchfenster eines sortierten Arrays (O(log n)), verlangt aber sortierte Eingaben. Bei einer Handvoll Elemente ist der Unterschied vernachlässigbar — bei großem Maßstab gewinnt die binäre Suche deutlich.Wie viele Vergleiche braucht die binäre Suche?
Höchstens etwa
log2(n) + 1: 10 Vergleiche decken 1.000 Elemente ab, 20 Vergleiche 1.000.000. Dieses logarithmische Wachstum macht sie zum Standard-Lookup auf sortierten Daten.Was ist der klassische Überlauf-Bug in der binären Suche?
Die Mitte als
(lo + hi) / 2 zu berechnen kann bei Ganzzahlen fester Größe überlaufen, wenn lo + hi das Maximum des Typs überschreitet. Die sichere Form ist mid = lo + (hi - lo) / 2. In Python spielt das keine Rolle (Ganzzahlen mit beliebiger Genauigkeit), aber in Java/C/C++ ist es ein echter, berühmter Bug.Ist die binäre Suche dasselbe wie ein binärer Suchbaum?
Sie teilen die Halbierungsidee, unterscheiden sich aber in der Struktur: Die binäre Suche ist ein Algorithmus auf einem sortierten Array, während ein binärer Suchbaum eine verkettete Datenstruktur ist, die ihre Schlüssel geordnet hält, sodass Suchvorgänge an jedem Knoten nach links oder rechts absteigen.
Verwandte Ressourcen
Mehr Visualisierungen
