Kenapa bug di binary search bertahan 20 tahun, padahal kodenya cuma lima baris?

Bayangin algoritma paling dasar yang diajarkan di minggu kedua kuliah: binary search. Cari angka di array terurut dengan membelah rentang jadi dua, berulang. Teorinya sesederhana itu. Tapi ada satu bug di dalamnya yang hidup diam-diam di hampir semua buku teks, library standar, dan kode produksi — selama sekitar dua dekade. Dan yang bikin geli: bug itu bukan di logikanya, tapi di satu operasi aritmetika yang kelihatannya terlalu sepele untuk salah.

Kode yang "benar" tapi salah

Versi klasik (disederhanakan):

int low = 0;
int high = a.length - 1;

while (low <= high) {
    int mid = (low + high) / 2;   // <-- biang keladi
    ...
}

Aman, kan? low + high cuma dua angka indeks. Masalahnya: low dan high adalah tipe bilangan bulat fixed-width (misal int 32-bit), yang maksimumnya 2.147.483.647. Kalau array-nya cukup besar — bayangkan low = 1.500.000.000 dan high = 1.500.000.001 — maka low + high = 3.000.000.001, melebihi batas int. Hasilnya bukan angka besar, tapi overflow: nilainya melingkar jadi bilangan negatif. Bagi dua → mid negatif → akses indeks di luar batas → crash atau hasil ngawur.

Kenapa bertahan lama?

Tiga alasan yang bikin bug ini "berumur panjang":

Butuh array raksasa untuk terpicu. Untuk int 32-bit, ukurannya harus mendekati 2 miliar elemen. Di era ketika binary search ditulis (1946, ide awalnya dari John Mauchly), bahkan menyimpan array sebesar itu mustahil. Jadi bug-nya secara harfiah tidak bisa muncul — sampai memori komputer tumbuh cukup besar. Bug-nya menunggu hardware menyusul.
Bug "warisan turunan." Binary search disalin dari buku ke buku, dari satu implementasi ke implementasi lain, tanpa pernah diuji ulang untuk skala baru. Kalau semua orang menyalin yang sama, semua orang mewarisi bug yang sama.
Kelihatan benar. (low + high) / 2 adalah cara paling intuitif menghitung titik tengah. Tidak ada yang "mencurigakan" secara visual. Bug yang butuh edge case raksasa untuk muncul nyaris tak pernah ditemukan lewat tes normal.

Yang mengejutkan

Pada 2006, Joshua Bloch — engineer di Google (sebelumnya di Sun, ikut menulis Java) — menulis blog berjudul "Extra, Extra — Read All About It: Nearly All Binary Searches and Mergesorts are Broken". Dia menemukan bug ini di implementasi binary search library standar Java, lalu melacaknya ke belakang dan menemukannya di hampir semua implementasi terkenal, termasuk versi di buku teks klasik Programming Pearls (Bentley). Lebih jauh: varian bug yang sama juga menginfeksi mergesort, karena algoritma itu memakai perhitungan titik tengah yang serupa.

Perbaikannya sepele:

int mid = low + ((high - low) / 2);   // tidak pernah overflow
// atau trik bit-shift:
int mid = (low + high) >>> 1;         // unsigned shift

Yang bikin miris: The Art of Computer Programming (Knuth) sudah lama memperingatkan soal overflow ini, dan Donald Knuth mencatat binary search benar-benar "diterbitkan" pertama kali pada 1946 — tapi butuh 60 tahun sampai semua implementasi populer benar-benar bersih.

Takeaway

"Kode yang benar untuk skala kecil belum tentu benar untuk skala besar."

Bug paling berbahaya bukan yang bikin error langsung — tapi yang kelihatan benar, disalin semua orang, dan baru meledak saat sistem tumbuh melewati asumsi lama. Binary search mengajarkan: just because it works, doesn't mean it's correct. Selalu tanya "apa yang terjadi kalau angka ini jadi jauh lebih besar?"

Sumber: Joshua Bloch, "Extra, Extra — Read All About It: Nearly All Binary Searches and Mergesorts are Broken", Google Research Blog, 2 Juni 2006. https://research.google/blog/extra-extra-read-all-about-it-nearly-all-binary-searches-and-mergesorts-are-broken/