Veri Yapısı ve Algoritmalar İkili Arama

İkili arama, çalışma zamanı karmaşıklığı Ο (log n) olan hızlı bir arama algoritmasıdır. Bu arama algoritması böl ve fethet ilkesine göre çalışır. Bu algoritmanın düzgün çalışması için veri toplama sıralı biçimde olmalıdır.

İkili arama, koleksiyonun en ortasındaki öğeyi karşılaştırarak belirli bir öğeyi arar. Bir eşleşme olursa, öğenin dizini döndürülür. Ortadaki öğe öğeden daha büyükse öğe, ortadaki öğenin solundaki alt dizide aranır. Aksi takdirde, öğe, ortadaki öğenin sağındaki alt dizide aranır. Bu işlem, alt dizinin boyutu sıfıra düşene kadar alt dizide de devam eder.

İkili Arama Nasıl Çalışır?

İkili aramanın çalışması için, hedef dizinin sıralanması zorunludur. İkili arama sürecini resimli bir örnekle öğreneceğiz. Aşağıdaki sıralı dizimizdir ve 31 değerinin konumunu ikili aramayı kullanarak aramamız gerektiğini varsayalım.

İlk olarak, bu formülü kullanarak dizinin yarısını belirleyeceğiz -

mid = low + (high - low) / 2

İşte 0 + (9 - 0) / 2 = 4 (4,5 tamsayı değeri). Yani, 4 dizinin ortasıdır.

Şimdi 4. lokasyonda saklanan değeri aranan değerle, yani 31 ile karşılaştırıyoruz. 4. lokasyondaki değerin 27 olduğunu buluyoruz, bu bir eşleşme değil. Değer 27'den büyük olduğundan ve sıralı bir dizimiz olduğundan, hedef değerin dizinin üst kısmında olması gerektiğini de biliyoruz.

Düşük değerimizi orta + 1'e çeviririz ve yeni orta değeri tekrar buluruz.

low = mid + 1
mid = low + (high - low) / 2

Yeni ortamız artık 7. Konum 7'de depolanan değeri hedef değerimiz 31 ile karşılaştırıyoruz.

7. konumda depolanan değer bir eşleşme değil, aradığımızdan daha fazlasıdır. Bu yüzden değerin bu konumun alt kısmında olması gerekir.

Dolayısıyla ortayı tekrar hesaplıyoruz. Bu sefer 5.

5. lokasyonda saklanan değeri hedef değerimizle karşılaştırıyoruz. Bir eşleşme olduğunu görüyoruz.

Hedef değer 31'in 5. konumda saklandığı sonucuna vardık.

İkili arama, aranabilir öğeleri yarıya indirir ve böylece yapılacak karşılaştırmaların sayısını çok daha az sayıya indirir.

Sözde kod

İkili arama algoritmalarının sözde kodu şöyle görünmelidir -

Procedure binary_search
   A ← sorted array
   n ← size of array
   x ← value to be searched

   Set lowerBound = 1
   Set upperBound = n 

   while x not found
      if upperBound < lowerBound 
         EXIT: x does not exists.
   
      set midPoint = lowerBound + ( upperBound - lowerBound ) / 2
      
      if A[midPoint] < x
         set lowerBound = midPoint + 1
         
      if A[midPoint] > x
         set upperBound = midPoint - 1 

      if A[midPoint] = x 
         EXIT: x found at location midPoint
   end while
   
end procedure

C programlama dilinde dizi kullanarak ikili arama uygulaması hakkında bilgi edinmek için lütfen buraya tıklayın .