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.
void SayiBul(int aranacakSayi, int[] dizi){
for(int i=0; i < dizi.lentgh(); i++){
if(aranacakSayi == dizi[i]){
cout << "Aradığınız sayı dizinin " << i << ". elemanında bulunmuştur." << endl;
return;
}
}
cout << "Aradığınız sayı dizide bulunmamaktadır." << endl;
}
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.
BinarySearch(Dizi[] , deger, bas, son){
if(son < bas)
return Bulunamadi
orta = (bas + son) / 2;
if(deger > Dizi[orta])
return BinarySearch(Dizi[], deger, orta+1, son);
else if(deger < Dizi[orta])
return BinarySearch(Dizi[], deger, bas, orta-1);
else return orta;
}
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.
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++
int BinarySearch(int dizi[], int bas, int son, int deger){
if (son >= bas){
int orta = (bas + son)/2;
if (dizi[orta] == deger)
return orta;
if (dizi[orta] > deger)
return BinarySearch(dizi, bas, orta-1, deger);
else return BinarySearch(dizi, orta+1, son, deger);
}
return -1;
}
Python
def binarySearch (dizi, bas, son, deger):
if son >= bas:
orta = (bas + son)/2
if dizi[orta] == deger:
return orta
elif dizi[orta] > deger:
return binarySearch(dizi, bas, orta-1, deger)
else:
return binarySearch(dizi, bas+1, son, deger)
else:
return -1
Java
class BinarySearch{
int binarySearch(int dizi[], int bas, int son, int deger){
if (son >= bas){
int orta = (bas + son)/2;
if (dizi[orta] == deger)
return deger;
if (dizi[orta] > deger)
return binarySearch(dizi, bas, orta-1, deger);
return binarySearch(dizi, orta+1, son, deger);
}
return -1;
}
}
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.
63