Javascript Algoritmaları – Binary Search
Binary search sıralı bir dizi içinde aradığımız değeri bulabilmek için çok verimli bir algoritmadır. Verilen sıralı diziyi tekrar tekrar 2 ye bölerek aramaya devam eder sonunda aradığı değerin index numarasını bulana kadar. Binary search kullanımı için bir örnek verecek olursak , diyelim ki Google Maps ile çalışıyorsunuz ve kullanıcıdan aldığınız bir mekan ismini DB den gelen sıralı listenizden bulup o mekanın koordinatlarını alıp haritada gostermek istiyorsunuz bunun için en verimli arama algoritması Binary Search olacaktır. Nedenini açıklayacak olursak linear arama da algoritma tüm listeyi bastan sona gezer ve bulmaya çalışırdı bu da binlerce mekan bilgisi içinden bir isim bulabilmek için tek tek bastan sona hepsini incelemesi gerektiği anlamına geliyor hem uzun hemde yorucu bir işlem ancak binary search ile bu binlerce mekanı tek tek kontrol etmek zorunda değiliz.
İnsanlara bir algoritmayı anlatırken bazı küçük detayları söylemeye gerek yoktur örneğin bir kek yapılmasını istediğimizde buzdolabını nasıl açması gerektiğini yada yumurtaları dolaptan çıkarıp nasıl kırmaları gerektiğini söylememize gerek kalmaz insan bu gibi küçük detayları kendisi tamamlayarak kek yapma işlemini tamamlayabilirler ancak bilgisayarda bu gibi küçük detaylar bilgisayar tarafından tamamlanamaz tüm detayların bilgisayara tanımlanması gerekir.
Programlama boyutunda algoritmaları uygulayabilmek için algoritmanın tüm detaylarını bilmek gerekiyor. Problem için girdiler nedir ? Çıktısı nedir ? Hangi değişkenler tanımlanmalı ? Bu değişkenler ne türde olmalı? Bir döngü olmalı mı ne gibi koşullarda olmalı gibi detaylar.
Hadi bu kadar boş yaptıktan sonra şu binary search e dikkatlide göz atalım. Buradaki ana fikir belirttiğimiz sayıyı bulabilmek için belirli aralıkları takip etmek. Diyelim ki bir tahmin oyunu oynuyoruz ve bu tahmin oyununda aklımızdan 1 ile 100 arasında bir sayı tutuyoruz. Ardından siz de bana tahminimizi söylüyorsunuz ve 25 diyorsunuz ve ben size Yukarı diyorum. Ardından siz 81 diyorsunuz bende size Aşağı diyorum. Şimdi biliyorsunuz ki sayı artık kırmızı ile işaretlediğimiz 26 ile 80 aralığında yani 25 ten küçük ve 81 den büyük sayıların hepsini elemiş olduk.
Her seferinde tahmininiz eğer doğru değilse kalan aralıktaki sayıları belli tahmin edilebilir bir aralığa bölerek devam ediyor. Üçüncü tahmininde53 diyorsunuz ve bende Aşağı diyorum yine ne yapmış olduk 26-80 aralığındaki sayıyı tekrar bölmüş olduk
Doğru sayıyı bulana kadar böyle sürüp giden ama sonunda sayıyı bulduğumuz bir oyun gibi çalışır Binary Search.
İşlem sırası yazacak olursak
1-Min = 1 ve Max = n
2-Max ve Min sayı aralığında bir integer bir değer tut
3-Eğer sayıyı bulduysan çık. Doğru tahmin
4-Eğer tutulan sayıdan düşük ise Min değişkenine tahmin edilen sayıya 1 ekleyip atama işlemini gerçekleştir.
5-Eğer tahmin edilen sayı tutulandan büyük ise o zaman Max değerini tahmin edilenden 1 çıkarıp atama işlemini gerçekleştir.
6-2 numaralı işleme geri dön.
See the Pen Binary Search by mzekiosmancik (@mzekiosmancik) on CodePen.