BinarySearch deki böcek(bug)

bilen bilir bu epey eski en hızlı arama algoritmasıdır. tabii sıralı dizilerde. yani diziniz doğru sort edilmişse ki bunun içinde ekleme işleminde ayarlar yaparız. sonuçda çok bilinen çok fazla olmasada aradabir kullanılması ihtimali mevcut olan bu algoritmada bir bug olmasını ben hiç beklemezdim

50 yaşını geçmiş bu algoritmada hata olması imkansız gibi görünebilir. buyrun örnek java implementasyon:

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: }

basitçe anlatmak gerekirse. aranan değeri diziyi ortadan ikiye bölerek arıyor. sonuçda sıralı olduğu için aranan şey ortanın üstü sonun altındadır veya tam tersi şeklinde duruma bakıp öyle geziyor bu durumda O(logn) de çalışıyor. detayları merak eden için.

mantık olarak bir yanlış görünmezken ben hatayı şurdan öğrendim. olay int de tıkanıyor. günümüz dizileri(array) kocaman olabilir ve kodda 6. satırdaki toplama işlemi integer veri tipinin limitlerinin(2³¹ - 1) üstünde bir değer verebiliyor. işte orda çatlıyor. ortama göre bu işlemin sonucu negatif değer verebiliyor ve dizinin dışında bir indis oluşturabiliyor. buda diziden veriyi alırken hataya sebep oluyor. yine aynı yazıda bunu çözmek için verilen yöntemler mevcut:

6: int mid = (low + high) >>> 1;

bu işlemi 6. satıra uygularsak sağlıklı olabilir. ama yinede emin değiliz test etmemiz lazım diye gidiyor linkli yazı.

ben okuduğumda çok şaşırdım ortam google olunca limitler zorlanıyor işte. demekki hala bilgisayar özellikle veri yapıları ve algoritmalar tam anlamıyla oturmuş değil. ben knuth'tan sonra ki kendisinin 3 ciltlik bir külliyatı computer science'ı vardır bu cilterin herhangi biri düşse kafa yarar bu konular tartışılmaz sanıyordum:)