Binary Search Algoritması

4 Mart 2011 by B.Selçuk ÖKSÜZ
Leave a reply »
WP Greet Box icon
Merhaba! Selcukoksuz.com adresine hoş geldiniz. Eğer yeni iseniz ve içeriğimizi takip etmek isterseniz RSS Abonesi Olabilirsiniz.
Mailinize onay mesajı gönderilecektir. Cevaplamayı unutmayınız.

Search yani İkili algoritmasında ana olay sıralı bir dizi içerisinde arama yapmamızdır. İkili arama algoritması sıralı dizimizi ortadan ikiye bölerek aranılan değerin bulunup bulunmadığını; eğer bulunmadı ise arananın orta elemandan büyük mü küçük mü olduğunu kontrol eder. Diyelim ki aranan orta değerden küçüktür. Bu sefer arama algoritmamız orta elemandan büyük olan kısmı tamamen yok sayarak orta elemandan küçük olan kısmı yeni diziymiş gibi kabul eder. Böylelikle dizimiz yarıya indirgenmiş olmuştur. Sonrasında tekrardan orta değerden küçük kısmı ikiye bölerek, aranılan değerin bulunup bulunmadığını kontrol eder. Yeni orta değer aranan eleman değilse, küçük mü büyük mü diye yeniden kontrol edilir. Ve bu işlem aranan değer bulununcaya yada tamamen dizi taranıncaya kadar devam eder.

Örnek;

Dizimiz ==> -5,-3,-1,0,3,8,10,90

Dizi uzunluğu 7 (indis değeri sıfırdan başlıyor)

  1. Aradığımız değer nedir ?  Aranan eleman 8
  2. 7/2=3,5 ve ortadan bölmemiz gereken indis 4 olur. Bu değer 3 değeridir.
  3. 3 benim aradığım değer mi? Hayır
  4. Aradığım sayı orta değer (3) büyük mü, küçük mü? Büyük
  5. Yeni aranacak kısımda ki değerlerim : 8,10,
  6. Tekrar bölüyoruz. 2/2=1 Orta değerim= 10
  7. 10 aradığım sayı mı? Hayır
  8. Aradığım sayı 10 dan büyük mü, küçük mü? Küçük
  9. Yeni aranacak kısımda ki değerlerim: 8
  10. Orta değerim sekiz. Aradığım değer mi? Evet

İkili arama algoritmasının mantıksal algoritması aşağıda ki şekilde çalışmaktadır.

  • Başlangıç(Sıfır) ve Bitiş(dizi değeri-1) değerleri işaretlenir
  • Kontrol: Aranan eleman
    • Başlangıç ve bitişe göre orta eleman aradığım eleman mı?
    • Orta = (başlangıç+Bitiş)/2
    • Evet ise aranan değeri bulduk
    • Hayır ise
      • Aranan>Orta eleman mı?
        • Başlangıcı değiştir = Orta+1
      • Aranan<Orta eleman mı?
        • Bitişi değiştir = Orta -1

Yukarıda ki mantık ile döngü içerisinde istediğimiz elemanı bulmaktayız. Algoritmanın temsili resmi aşağıdaki gibidir.

Konu ile alakalı örnek uygulamayı daha önceden paylaşmıştım(Binary Search Uygulaması)

Ufaktan örnek bir fonksiyon vereyim;

int IkiliArama(int dizi[],int aranan)
{
   int baslangic = 0, bitis = diziboyutu-1, orta, bulunanindis = -1,

   while((bulunanindis==-1) && (baslangic<=bitis))
   {
       orta=(baslangic+bitis)/2;
       if(aranan==dizi[orta])
          bulunanindis=orta;
       else
       {
           if(aranan>dizi[orta])
               baslangic=orta+1;
           else
               bitis = orta-1;
       }
    }
    return bulunanindis;
}

Yazar Hakkında

Bilgisayarla yaşamayı bir tarz olarak benimsemiş, teknoloji ile tamamen içli dışlı bir; web tasarımcı, yazılımcı, donanımcı, blog yazarı ve bilgisayar mühendisidir.
B.Selçuk ÖKSÜZ
B.Selçuk ÖKSÜZ kullanıcısının tüm yazıları.

Arama Sorguları

  • algoritma örnekleri (50)
  • algoritma (49)
  • ikili arama algoritması (37)
Advertisement

Bu Yazıyı Beğendiniz Mi?

1

1 comment

  1. Mahmut İnci dedi ki:

    Teşekkürler kodlaman okunaklı kaliteli kod yazıyorsun başarılarının devamını dilerim.Bu arada işime yaradı ; )

Bir Cevap Yazın

Sizin Yorumunuz Nedir?

%d blogcu bunu beğendi:
Gizlilik Hakları