Fallstricke der Binärsuche: Überlauf des Mittelpunkts und Off-by-one-Grenzen

Worum es geht

Die Binärsuche findet eine Position in sortierten Daten, indem sie den infrage kommenden Bereich wiederholt halbiert. Drei Fehler treten immer wieder auf. Erstens der Überlauf des Mittelpunkts: Der zitierte Google-Research-Beitrag beschreibt, wie (low + high) / 2 in der binarySearch-Methode des JDK versagt, sobald die Summe den maximalen int-Wert übersteigt, und nennt low + ((high - low) / 2) oder (low + high) >>> 1 als Korrektur. Zweitens die Grenzkonvention: Ob high inklusiv oder exklusiv ist, bestimmt die Schleifenbedingung und die Aktualisierungen; das Vermischen der Konventionen führt zu Endlosschleifen oder einem übersprungenen Element. Drittens Duplikate: Pythons bisect dokumentiert bisect_left (Einfügeposition vor gleichen Einträgen) und bisect_right (danach) – das ist der Unterschied zwischen «erster Treffer» und «Position nach dem letzten Treffer». Gos sort.Search umgeht das meiste davon, indem es nach dem kleinsten Index in [0, n) fragt, an dem ein monotones Prädikat wahr wird.

Warum es wichtig ist

Die Routine taucht in Paginierungs-Cursorn, Zeitreihen-Lookups, Versionsbereichsprüfungen, Suchen im Stil von git bisect über Builds und vielen «finde das erste, das fehlschlägt»-Aufgaben auf. Eine falsche Grenze bleibt unbemerkt: Ergebnisse weichen nur bei manchen Eingaben um eins ab, typischerweise beim ersten oder letzten Element.

So wird es angewendet

• Die Bibliotheksfunktion bevorzugen (bisect, sort.Search, Arrays.binarySearch); eine eigene nur schreiben, wenn das Prädikat kein Array-Lookup ist.
• Die Prädikatform verwenden: den ersten Index finden, an dem pred(i) wahr ist, wobei pred über den Bereich hinweg erst falsch, dann wahr sein muss. Untere Grenze, obere Grenze und «erste fehlschlagende Version» sind alles Ausprägungen davon.
• Ein halboffenes Intervall verwenden: lo, hi = 0, n; while lo < hi: mid = lo + (hi - lo) // 2; if pred(mid): hi = mid else lo = mid + 1; return lo. Das + 1 im else-Zweig garantiert Fortschritt.
• Die Randfälle testen: leere Eingabe, ein Element, Ziel unter dem ersten und über dem letzten, alle Elemente gleich, Ziel an Index 0 und n-1.
• Prüfen, dass die Daten unter demselben Vergleich sortiert sind, der für die Suche verwendet wird (bisect mit key= muss zum Sortierschlüssel passen).

Stolpersteine

Python-Integer laufen nicht über, aber die Grenzfehler bleiben bestehen. Eine Suche über Floats bricht bei Vorhandensein von NaN, weil Vergleiche dann keine Ordnung mehr bilden. Daten, die nach Locale-Kollation sortiert, aber byteweise durchsucht werden, sind für die Suche nicht sortiert. bisect_left gibt bei fehlenden Werten eine Einfügeposition zurück, nicht -1: mit i < len(a) and a[i] == x prüfen. Die Binärsuche auf einer verketteten Liste ist linear, weil die Indizierung es ist.