binary-search

Binary Search Algoritması

Merhaba arkadaşlar,
Mobilhanem.com üzerinden anlattığımız/yayınladığımız Algoritma Eğitimleri serimize devam ediyoruz. Bu dersimizde ise Binary Search Nedir sorusuna cevap vermeye çalışacağız.

Binary Search Nedir?

Evet arkadaşlar ilk iki dersimizin ardından üçüncü derse başlıyoruz ve ilk algoritmamız Binary Search algoritmasına geçiyoruz.

İngilizce bilen arkadaşlar zaten algoritmanın isminde geçen Search kelimesinden arama ile ilgili bir kavram olduğunu anlamıştır. Bu algoritmamız en temel arama algoritmalarından biridir. İnternet ve bilgisayar dünyasında kimi zaman milyarlarca hatta trilyonlarca verilerle işlem yapmak durumunda kalabiliyoruz. Gün geçtikçe artan veriler üzerinde arama yapmak başlı başına bir dert olabiliyor.

Bir örnek vermek gerekirse bir milyon uzunluğundaki sayı dizisi içinde bir sayı aramak istersek aklınıza gelecek ilk yöntem şöyle olacaktır ki: Diziyi baştan sona gezen bir for veya while döngüsü ile dizinin her elemanında if ile kontrol ederek sayının bizim aradığımız sayıya eşit olup olmadığına bakmak olacaktır. Hemen bu kodumuzun bir örneğini yazalım aşağıya.

Basit bir algoritma analizi yaparsak yazdığımız for döngüsü en kötü ihtimalde dizinin sonuna kadar gideceği için dizinin uzunluğu kadar işlem yapacaktır yani zaman karmaşıklığı O(N)’dir.

Birazdan anlatacağım Binary Search algoritmasında ise bu karmaşıklığı çok daha aşağılara indirerek verimli bir algoritma yazacağız. Ancak bu algoritmayı kullanabilmek için dizimizin bazı şartları sağlaması gerek. En önemlisi dizimizin küçükten büyüğe sıralı olması gerek. Bu, algoritmanın çalışması için olmazsa olmaz kuraldır. Yani sıralı olmayan bir dizide Binary Search yöntemini kullanarak eleman aramaya çalışırsanız malesef başarılı olamayacaksınız.

Şimdi algoritmanın kaba kodunu vereyim daha sonra elimden geldiğince açıklamaya çalışayım.

 

Binary Search Nasıl Çalışır?

Şimdi bizim amacımız Dizi[] isimli sayı dizisinde ‘deger’ elemanı var mı? Varsa dizinin kaçıncı elemanı? Sorularına cevap vermek.

Elimizdeki tek veri ise bu dizinin küçükten büyüğe doğru sıralı olduğu.

O zaman şöyle bir çıkarımda bulunalım. Mesela aradığımız eleman dizinin 6. elemanından büyük ise biz diyebiliriz ki ilk 5 elemandan da kesinlikle büyüktür. Çünkü biliyoruz ki dizi sıralı. 6. elemandan büyük olan bir sayı asla ilk 5 elemandan küçük olamaz. Yani boş yere ilk 5 elemana tek tek aradığımız değere eşit mi diye bakmamıza gerek yok. Çünkü biliyoruz ki aradığımız değer kesinlikle daha büyük.

Bu örneği biraz koda dökersek, BinarySearch fonksiyonunda tuttuğumuz baş ve son değerleri bizim aradığımız elemanın hangi aralıkta olduğunu gösteriyor. Fonksiyonumuzun ilk satırında dediği gibi eğer son değerimiz baş değerinden geride kalırsa demektir ki aralığı sıfıra kadar indirmemize rağmen biz bu değeri bulamamışız. Böylelikle daha fazla arama yapmadan direk olarak “Değer bulunamadı” çıktısını döndürebiliriz.

Fonksiyonumuzun 2. satırına geçersek orta diye yeni bir değişken ürettim bunun içine de baş ve sonun orta noktasını hesaplayıp atadım. Şimdi alttaki if kontrollerinde bu orta değeri kullanarak aradığımız elemanın nerede olabileceği konusunda fikir üretelim.

İlk if kontrolüm  aradığım değerin ortadaki elemandan büyük olup olmadığını kontrol ediyor. Eğer büyükse yukardaki örneğe benzer olarak diyebiliriz ki aradığımız eleman kesinlikle ortadan daha ileri bir değerde. Çünkü biz biliyoruz ki ortadan önceki değerlerin hepsi aradığımız değerden küçük. Böylelikle fonksiyonumuzun aralığını küçülterek (orta+1,son) aralığına daraltıyoruz.

İkinci if kontrolüm ise aradığım değerin ortadaki elemandan küçük olup olmadığını kontrol ediyor. Eğer küçükse biz ortadan sonraki elemanlardan da küçük olacağı çıkarımını yapabiliriz. Böylelikle aralığımızı (bas,orta-1) aralığına daraltıyoruz.

Bu iki if kontrolünden de olumsuz cevap aldıysak kodumuz else kısmına düşüyor. Değerimiz orta değerden küçük de değil büyük de değilse, bu değer ortadaki değere eşit olmak zorundadır. Yani biz sayımızı bulmuşuz. Geriye sadece dizide kaçıncı eleman olduğunu tutan orta elemanı döndürmek kalmış.

Binary Search’in Karmaşıklık Hesaplaması

Böylelikle her seferinde dizimizin aralığını yarı yarıya indirdiğimiz için kontrol ettiğimiz değer çok daha az oluyor. Buradaki maliyet hesaplamalarını yaparken “yarı yarıya indirme” kavramı çok önemli. Bu bize anlatıyor ki her seferinde dizinin kalan parçasının yarısını kontrol etmeden es geçebiliyoruz.

Bu nedenle Binary Search Algoritmasının zaman karmaşıklığı O(log N) ‘ dir.

Sayısal örnek vermek gerekirse:

1 000 elemanlı bir dizi için en kötü ihtimalle 10 işlem yapılır. Aynı şekilde:
10 000 için 13
100 000 için 16
1 000 000 için 19
1 000 000 000 için 30 işlem yapmak yeterli olacaktır.

O(log N) ile O(N) Arasındaki farkı aşağıdaki görselden görebilirsiniz.

binary search

 

1 000 000 000 uzunluğundaki dizide normal bir arama işlemi uygulasaydık 30 yerinde tam 1 000 000 000 işlem yapmak durumunda kalacaktık. Ve bilgisayarımız bu kadar işlem yapmamıza müsade etmeyecekti.
Buradan da anlaşılacağı üzere bir problemi aklımıza gelen ilk yöntemle çözmek ile verimli yöntemle çözmek arasında dağlar kadar fark vardır.

Yazımı sonlandırmadan önce Binary Search algoritmasını bir kaç popüler yazılım dilinde kodlayalım.

C++

 

Python

Java

Okuduğunuz için teşekkürler umarım faydalı olmuşumdur. Takıldığınız noktaları ve her türlü sorularınızı aşağıdan veya Soru Cevap kısmından sormayı lütfen eksik etmeyin. Bir sonraki Algoritma Eğitiminde görüşmek üzere. Sağlıcakla kalın.

Tüm Algoritma Derslerimiz İçin tıklayınız.

Hasan Bal

Competitive Programmer

Web Developer

12 Yorum

  • Hocam 1 sorum olacaktı.
    Diyelim elimizde bir dizi var ve sıralı değil. Dolayısıyla Binary Search yapamacağız.
    Böyle bir durumda Linear Search mü yapmak mantıklı yoksa diziyi sıralı bir hale sokup binary search mü yapmak mantıklı?

    • Öncelikle bu kaliteli ve güzel sorunuz için teşekkür ederim. Sorunun cevabı değişkendir. Eğer çok fazla sayıda arama işlemi yapılacaksa diziyi sıralayıp binary search yapmak daha verimli. Bunun yanı sıra az sayıda arama işlemi yapılacaksa diziyi sıralamak yerine linear search daha mantıklıdır. İlerideki sıralama algoritmaları dersimizde bu konuyu sayısal olarak da cevaplayacağım.

  • Hocam güzel anlatım için teşekkürler. 1000 elemanlı bir dizide N=1000. Bunun için log 1000 hesablanmalıdır. log 1000 = 3 deyilmi?

    • Hocam burada her seferinde diziyi 2’ye boldugumuz icin log2 tabaninda hesaplama yapmamiz gerek. Yani log2(1000) yaklasik 10’a esittir. Ilginiz icin tesekkurler.

  • Hocam kolay gelsin. Ôrnek java kodun da dizinin ortadaki değeri aranan değerden küçüktür koşulu için if bloğu konulmamış acaba nedeni nedir

    • Merhaba, zaten o fonksiyonun icindeki 2 if ifadesi esitlik ve buyukluk durumunu kontrol ediyor. Eger iki if’in icindeki return’e de girmezse kucuk oldugunu biliyoruz ve en alttaki return’u kucuk durumu icin yaziyoruz. En alttaki return’un ustune kucuk mu diye kontrol etmek icin if blogu koyabilirisiniz. Ancak sonucta herhangi bir degisiklik olmayacaktir.

  • Hocam eger listemiz 14 elemanli ise konuyu anladim. Ama 13 elemanli ise nasil dusunmemiz gerek? Ortadaki Index i nasil bulacagiz? Tesekkur ederim.

    • Merhaba,
      13 eleman icin ilk durumda bas=1 son=13. Orta’yi hesaplamak icin bunlari toplayip 2’ye bolmeliyiz. Bu nedenle baslangicta orta=7. Daha sonra ortadaki elemanin degerine gore saga veya sola gidecegiz. Bu sayede butun gerekli elemanlar gezilmis olacak.
      Eger yine anlasilmadiysa takildiginiz noktayi daha ayrintili anlatma sansiniz var mi acaba? Iyi calismalar.

      • hocam turkcem biraz zayif…kusura bakmayin.
        (min+max)/2
        int min =1;
        int max = 14

        biz int aliyoruz sonucu, 7.5 oluyor 7. bu kisimda sorun yasiyorum, 7 orta mi oluyor bu durumda?

        birde hocam, binarySearch() metodu var API de. Bu algoritma ile binarySearch() keza linearSearch() arasindaki fark nedir? Hazir bir metod varken neden yazmaliyiz bu algoritmayi?
        birde yaptiginiz zaman hesaplamalarini hic anlamiyorum, nasil yapiyorsunuz bilmiyorum 🙂 ama cok iyi yapiyorsunuz, iyi birsey yapiyorsunuz, sagolun.

        • İlk soruna cevap vermek gerekirse evet orta 7 oluyor.

          Binary Search zaten bir çok dilde hazır bir fonksiyon olarak bulunur. Ancak algoritmanın çalışma mantığını öğrenmek için öğrenmeliyiz.

          Binary Search O(logN)’de çalışırken Linear Search O(N)’de çalışır. Ancak dikkat etmemiz gereken nokta, binary search yalnızca sıralı dizilerde uygulanabilir.

          Zaman karmaşıklığı, her seferinde kalan diziyi yarıya böldüğümüzden dolayı log2 N olmaktadır.

Haftalık Bülten

Mobilhanem'de yayınlanan dersleri haftalık mail almak ister misiniz?