Saya ingat dengan jelas kuliah Algoritma pertama Jon Bentley di CMU, di mana dia bertanya kepada kami semua calon Ph.D. siswa untuk menulis pencarian biner, dan kemudian membedah salah satu implementasi kami di depan kelas. Tentu saja hal ini rusak, begitu pula sebagian besar implementasi kami. Hal ini memberikan kesan yang nyata pada saya, begitu pula perlakuan terhadap materi ini dengan sangat indah Mutiara Pemrograman (Addison-Wesley, 1986; Edisi Kedua, 2000). Pelajaran utamanya adalah mempertimbangkan invarian dalam program Anda dengan cermat.
Maju cepat ke tahun 2006. Saya terkejut mengetahui bahwa program pencarian biner yang Bentley terbukti benar dan kemudian diuji di Bab 5 buku Mutiara Pemrograman mengandung bug. Setelah saya memberi tahu Anda apa itu, Anda akan mengerti mengapa ia lolos dari deteksi selama dua dekade. Agar Anda tidak berpikir saya memilih Bentley, izinkan saya memberi tahu Anda bagaimana saya menemukan bug tersebut: Versi pencarian biner yang saya tulis untuk JDK mengandung bug yang sama. Hal ini dilaporkan kepada Sun baru-baru ini ketika hal itu merusak program seseorang, setelah menunggu selama sembilan tahun atau lebih.
Jadi apa bugnya? Berikut pencarian biner standar, di Java. (Itu salah satu yang saya tulis untuk java.util.Arrays):
1: public static int binarySearch(int() a, int key) {
2: int low = 0;
3: int high = a.length - 1;
4:
5: while (low <= high) {
6: int mid = (low + high) / 2;
7: int midVal = a(mid);
8:
9: if (midVal < key)
10: low = mid + 1
11: else if (midVal > key)
12: high = mid - 1;
13: else
14: return mid; // key found
15: }
16: return -(low + 1); // key not found.
17: }
Bugnya ada di baris ini:
6: int mid =(low + high) / 2;
Di dalam Mutiara Pemrograman Bentley mengatakan bahwa garis analog “menetapkan m ke rata-rata l dan u, dipotong hingga bilangan bulat terdekat.” Sepintas lalu, pernyataan ini mungkin tampak benar, namun gagal untuk nilai-nilai yang besar int variabel low Dan high. Secara khusus, gagal jika jumlahnya low Dan high lebih besar dari nilai positif maksimumnya int nilai (231 – 1). Jumlahnya meluap ke nilai negatif, dan nilainya tetap negatif bila dibagi dua. Di C hal ini menyebabkan indeks array keluar batas dengan hasil yang tidak dapat diprediksi. Kalau di Jawa lempar ArrayIndexOutOfBoundsException.
Bug ini dapat muncul pada array yang panjangnya (dalam elemen) adalah 230 atau lebih besar (kira-kira satu miliar elemen). Hal ini tidak terbayangkan pada tahun 80an Mutiara Pemrograman telah ditulis, tetapi hal ini umum terjadi saat ini di Google dan tempat lain. Di dalam Mutiara PemrogramanBentley mengatakan “Sementara pencarian biner pertama diterbitkan pada tahun 1946, pencarian biner pertama yang bekerja dengan benar untuk semua nilai N baru muncul pada tahun 1962.” Sebenarnya, sangat sedikit versi yang benar yang pernah diterbitkan, setidaknya dalam bahasa pemrograman umum.
Jadi apa cara terbaik untuk memperbaiki bug tersebut? Inilah salah satu caranya:
6: int mid = low + ((high - low) / 2);
Mungkin lebih cepat, dan bisa dibilang jelas adalah:
6: int mid = (low + high) >>> 1;
Di C dan C++ (di mana Anda tidak memilikinya >>> operator), Anda dapat melakukan ini:
6: mid = ((unsigned int)low + (unsigned int)high)) >> 1;
Dan sekarang kita tahu pencarian biner bebas bug, bukan? Ya, kami menduga kuat demikian, tapi kami tidak tahu. Tidaklah cukup hanya membuktikan suatu program benar; Anda harus mengujinya juga. Selain itu, untuk benar-benar yakin bahwa suatu program benar, Anda harus mengujinya untuk semua kemungkinan nilai masukan, namun hal ini jarang dapat dilakukan. Dengan program bersamaan, keadaannya bahkan lebih buruk lagi: Anda harus menguji semua keadaan internal, yang, untuk semua tujuan praktis, tidak mungkin dilakukan.
Bug pencarian biner berlaku sama untuk mergesort, dan algoritma bagi-dan-taklukkan lainnya. Jika Anda memiliki kode yang mengimplementasikan salah satu algoritma ini, perbaiki sekarang sebelum meledak. Pelajaran umum yang saya ambil dari bug ini adalah kerendahan hati: Sulit untuk menulis kode terkecil sekalipun dengan benar, dan seluruh dunia kita berjalan pada potongan kode yang besar dan rumit.
Kami, para programmer, memerlukan semua bantuan yang kami bisa dapatkan, dan kami tidak boleh berasumsi sebaliknya. Desain yang cermat itu bagus. Pengujian itu bagus. Metode formal sangat bagus. Ulasan kode sangat bagus. Analisis statis sangat bagus. Namun tidak satupun dari hal-hal ini saja yang cukup untuk menghilangkan bug: Mereka akan selalu bersama kita. Sebuah bug dapat bertahan selama setengah abad meskipun kita telah melakukan upaya terbaik untuk memusnahkannya. Kita harus membuat program dengan hati-hati, defensif, dan tetap waspada.
Pembaruan 17 Februari 2008: Terima kasih kepada Antoine Trux, Anggota Utama Staf Teknik di Nokia Research Center Finlandia karena telah menunjukkan bahwa usulan perbaikan awal untuk C dan C++ (Jalur 6), tidak dijamin berfungsi sesuai standar C99 yang relevan (STANDAR INTERNASIONAL – ISO/IEC – 9899 – Edisi kedua – 01-12-1999, 3.4.3.3), yang mengatakan bahwa jika Anda menambahkan dua besaran bertanda dan mendapatkan overflow, hasilnya tidak ditentukan. Standar C yang lebih lama, C89/90, dan Standar C++ keduanya identik dengan C99 dalam hal ini. Sekarang setelah kita melakukan perubahan ini, kita tahu bahwa programnya benar;)
