DAA - İkili Arama

Bu bölümde, bölme ve yönetme yöntemine dayalı başka bir algoritmayı tartışacağız.

Sorun bildirimi

İkili arama, sıralı bir dizide gerçekleştirilebilir. Bu yaklaşımda, bir elemanın indeksixelemanın eleman listesine ait olup olmadığı belirlenir. Dizi sıralanmamışsa, konumu belirlemek için doğrusal arama kullanılır.

Çözüm

Bu algoritmada, elementin x bir dizide saklanan bir sayı kümesine aittir numbers[]. Neredel ve r arama işleminin gerçekleştirilmesi gereken bir alt dizinin sol ve sağ dizinini temsil eder.

Algorithm: Binary-Search(numbers[], x, l, r)
if l = r then  
   return l  
else 
   m := ⌊(l + r) / 2⌋ 
   if x ≤ numbers[m]  then 
      return Binary-Search(numbers[], x, l, m) 
   else 
      return Binary-Search(numbers[], x, m+1, r)

Analiz

Doğrusal arama çalışır O(n)zaman. İkili arama sonucu verirkenO(log n) zaman

İzin Vermek T(n) bir dizide en kötü durumda karşılaştırmaların sayısı n elementler.

Bu nedenle

$$ T (n) = \ start {case} 0 & if \: n = 1 \\ T (\ frac {n} {2}) + 1 & aksi halde \ end {case} $$

Bu tekrarlama ilişkisini kullanarak $ T (n) = log \: n $.

Bu nedenle, ikili arama $ O (log \: n) $ time kullanır.

Misal

Bu örnekte, 63 öğesini arayacağız.