Ikili arama

İkili arama verimli bir — karmaşıklık tahmini O(log2(n)) iken geleneksel sıralı aramada O(n) bulunur. Bu, örneğin 1024 öğelik bir dizi için, en kötü durumda, istenen öğenin dizide olmadığı bir doğrusal aramanın 1024 öğenin tamamını işleyebileceği anlamına gelir. \(log_2(1024) = 10\) öğelerini işlemek için ikili arama yeterlidir. Bu sonuç, döngünün ilk adımından sonra arama alanının 512 öğeye, ikinci adımdan sonra 512 öğeye kadar daralması nedeniyle elde edilir. 256'ya kadar vs.

Uygulama

güle güle (sağ – sol > 1)  // Sağ kenarlık solun sağında olduğu sürece
nc
  orta = (sol + sağ) /< /span> 2; // Arama alanının ortası
  eğer (A[middle] >= b) sonra
    sağ = orta; // Sağ kenarlığı taşıyın
  aksi takdirde
    sol = orta; // Aksi takdirde sol kenarlığı hareket ettirin
cc
if (A[right] == X) o zaman
  doğru çıktı;
aksi takdirde
  çıktı -1;