İkili Arama ( Binary Search )

İspanyadan selam 🙂 Bir önceki yazıda Linear Search ten bahsetmiştim bu yazıda ise Binary Search ‘ün java ve python implementlerini yapacağız.

İnternette birçok yerde Binary Search in anlatımı bulabilirsiniz ama ben yinede dayanamadım , anlatıyım 🙂

Yukarıda bir örnek dizi bulabilirsiniz. İlk kural ! Binary Search ‘in çalışabilmesi için dizinin sıralanmış dizi olması gereklidir.

Binary Search kısaca şunu yapar ; Dizinin ordasındaki değeri alır , aranan değer ile karşılaştırır eğer aranan değer  ortadaki değerden büyükse diziyi ikiye böler ve ortadaki değerle beraber solunda kalanları direk atlar. Sağ tarafta kalanları yeni dizi gibi düşünebilirsiniz.

Aynı şekilde de ortadaki değer aranan değerden büyük olduğu zamanda bu sefer sağ taraftakiler atlar ve sol tarafı yeni bir dizi gibi düşünebilirsiniz.

Bu böyle Left ve Right eşit oluncaya kadar devam eder her seferinde dizi 2 ye bölünür. Left ve Right değerleri eşit olduğunda arana değer bulunmuş olur.

Dikkat edilmesi gereken nokta ise , aslında diziyi 2 ye bölüp yeni bir dizi oluşturmuyor sadece Left yada Right imleçlerini kaydırarak yeni bir dizi gibi değerlendiriyor.

Yukarıda aranan değerin 5 olduğunu varsayarsak , Right imlecini sola doğru kaydırmamız gerekiyor yani eski ortadaki değerin bir soluna. Eğer aranan değer 15 olsaydı Left imlecini bu sefer eski ortadaki değerin bir sağına kaydıracaktık.

 

Aşağıda Java ve Python örneklerini bulabilirsiniz.

 

Binary Search ‘in Big Oh notasyonu ile gösterimi de O(log n) dir.Aslında log 2 tabanındadır ama o genelde yazılmaz. Logaritma nasıl geldi diye merak edecek olursanız, dizi her seferinde n/2 defa kontrol ediliyor.Yani T(n) fonksiyonu n/2 + k  dır. Bu bölme T(1) e kadar devam eder. Sondan başa doğru gelecek olursak bunu 1*2^k=n gibi yazabiliriz buradan da k = log n gelir.