1. İkili Arama (Binary Search)

BINARY SEARCH (İKİLİ ARAMA)

Bilgisayar bilimlerinde binary search bir bilgi kaynağı veya veri yapısı üzerinde problemi her adımda iki parçaya bölerek yapılan arama algoritmasıdır. Divide and Conquer mantığıyla çalışır. Binary search kullanılabilmesi için verilerin sıralı olması şarttır. Binary search’te veri kümesinin en ortasına bakılır. Eğer aradığımız değer en ortadaki değerden küçükse aramaya küçük taraf yani sol taraftan, büyükse sağ taraftan devam edilir. Aranan değer bulunana kadar bu işlem küçük parçalarda da uygulanır. Böylece her bir searchte veri kümesinin yarısını elemiş oluşuruz.

Örnek olarak elimizde   9, 7, 6, 4, 3, 2, 1   sıralı dizisi olsun.   Bu dizi arasında 6 sayısını aralım.

1.  Dizinin ortasına bakılır  .  4 ? 6  –> 4 < 6  . Aranan değer büyük olduğundan dizinin sağ tarafı dikkate alınmaz ve sol taraf üzerinden arama işlemine devam edilir. Böylece veri kümemizi yarı yarıya küçültmüş oluruz.

2.  9 , 7 , 6 .. bu sefer elimizde kalan dizinin tam ortasına bakılır. 7 ? 6 –> 7 > 6. Aranan değer küçük olduğundan arama işlemine sağ taraftan devam edilir.

3.  6 = 6 .. Aranan değer bulunmuş olur.

DİZİDE ORTANCA DEĞERİN BULUNMASI

      9, 7, 6, 4, 3, 2, 0,1,-1,-2  sıralı dizimiz olsun. dizinin indisleri ise 0, 1, 2, 3, 4, 5, 6, 7, 8, 9

ortanca değer bulunurken     uç değerlerin indisleri toplamı 2’ye bölünür .  4. veya 5. indexi ortanca değer alabilirsiniz.

      9 ,  7 ,  6 ,  4 ,  ,  2 ,  0 , 1 , -1 , -2   ->   (0 + 9 )/ 2 = 4.5   ortanca değer 4. veya 5. indis alınıp aranan değer ile kıyaslanır.

aranan değer bulunamassa tekrar uç değerlere aynı işlem uygulanır.

      9 , 7 , 6 , 4 , 3   ->   (0+4)/2 = 2  aramaya sol tarafta devam edersek ortanca değer 2. indis alınıp arana değer ile kıyaslanır.

aranan değer bulunamassa tekrar uç değerlere aynı işlem uygulanır.

      9 , 7 6      ->   (0+1)/2 = 0.5    aramaya sol tarafta devam edersek ortanca değer 1. indis alınıp arana değer ile kıyaslanır.

Eğer aranan değer dizide bulunamassa bunun uyarısı verilir.

      9

BINARY SEARCH C# IMPLEMENTASYONU

Aşağıdaki kod  ele alındığında problem her seferinde aranan sayıya göre ortadan ikiye bölünmektedir. Bu anlamda problemin log
2(n) adımda çözülmesi beklenir.

Best case – O (1) Kıyaslama :   Best casede, aranan değer dizinin tam ortasındadır ve tek aramada bulunur.

Worst case – O (log n) Kıyaslama : Worst case, aranan değer dizide bulunamaz ve O(logn) karmaşıklığına sahiptir.

public int IkiliArama(int arananSayi,int[] sayilar)
{   
     int baslangic = 0, bitis = sayilar.GetUpperBound(0), orta = (baslangic+bitis)/2;//baslangic indisi,bitis indisi ve ortanca indis belirlenir.

  while(bitis-baslangic>1)  //dizide tek eleman kalınca döngü biter.
  {
      orta = (baslangic+bitis)/2;

      if(sayilar[orta]>arananSayi)//ortanca sayı aranan sayıdan büyük ise veri kümesini küçük tarafın sınırlarıyla daralt
      {
        bitis = orta;
      }
      else if(sayilar[orta]//ortanca sayı aranan sayıdan küçük ise veri kümesini büyük tarafın sınırlarıyla daralt
      {
        baslangic = orta;
      }
      else
      {
        return orta;
      }
  }
     return -1;

}