Binary Search
Die binäre Suche vergleicht mit dem mittleren Element eines sortierten Arrays und halbiert den Bereich jedes Mal, wodurch ein Ziel in O(log n) gefunden wird; sie ist der grundlegende effiziente Suchalgorithmus.
Zweck
Elemente in sortierten Daten effizient finden und logarithmische Komplexität auf die Suche anwenden.
Mechanismus
Das Intervall [lo, hi] wird mit mid=(lo+hi)/2 verwaltet; mid wird mit dem Ziel verglichen: bei Gleichheit zurückgeben, sonst bei kleinerem Wert die rechte Hälfte, bei größerem die linke Hälfte durchsuchen. Das Intervall halbiert sich pro Schritt, was O(log n) ergibt. Sortiertheit ist Voraussetzung. Varianten: untere Schranke, obere Schranke, Einfügepunkt.
Anwendungsfälle
- Suche in sortierten Arrays
- B+-Baum-Indizes in Datenbanken
- Bisect in der Versionsverwaltung
- Nullstellensuche von Funktionen (Bisektion)
Beispiele
- Eingabe
Search 5 in [1,3,5,7,9]OutputIndex 22 comparisons
Häufige Fehler
- lo+hi integer overflow
- Use lo+(hi-lo)/2
Verwandte Begriffe
Sorting Algorithm
Sortieralgorithmen bringen Elemente in eine Reihenfolge — Quicksort, Mergesort und Heapsort sind verbreitet — mit Komplexitäten von O(n log n) bis O(n²). GLOSSAR
Big O Notation
Die Big-O-Notation beschreibt die asymptotische obere Schranke einer Funktion und dient der Analyse der Zeit-/Speicherkomplexität von Algorithmen unter Vernachlässigung von Konstanten und niedrigeren Termen. GLOSSAR
Hash Table
Eine Hashtabelle bildet Schlüssel über eine Hashfunktion auf ein Bucket-Array ab und bietet im Schnitt O(1) bei Suche/Einfügen/Löschen; sie gehört zu den meistgenutzten Datenstrukturen. GLOSSAR