Schock! Fast alle binären Such- und Mergesorts sind fehlerhaft
2025-01-11
Der Google-Softwareentwickler Joshua Bloch enthüllte einen fast zwei Jahrzehnte alten Bug, der in binären Suchalgorithmen lauert, sowohl im JDK als auch in Jon Bentleys "Programming Pearls"! Der Bug stammt von der Zeile `int mid = (low + high) / 2;`, die einen Integer-Überlauf und ArrayIndexOutOfBoundsException verursacht, wenn die Summe von `low` und `high` den maximalen positiven Integerwert überschreitet. Dieser Bug manifestiert sich nur bei riesigen Datensätzen und ist daher in der heutigen Big-Data-Welt besonders gefährlich. Der Artikel untersucht verschiedene Lösungsansätze und betont, dass Bugs auch bei gründlichen Tests und Beweisen bestehen bleiben können, und mahnt Programmierer zu Vorsicht und Bescheidenheit.