DAA — бинарный поиск

В этой главе мы обсудим другой алгоритм, основанный на методе «разделяй и властвуй».

Постановка задачи

Двоичный поиск может быть выполнен по отсортированному массиву. В этом подходе индекс элемента x определяется, если элемент принадлежит списку элементов. Если массив не отсортирован, для определения позиции используется линейный поиск.

Решение

В этом алгоритме мы хотим выяснить, принадлежит ли элемент x к набору чисел, хранящихся в массиве numbers [] . Где l и r представляют левый и правый индекс подмассива, в котором должна выполняться операция поиска.

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) 

Анализ

Линейный поиск выполняется за O (n) раз. В то время как бинарный поиск выдает результат за O (log n)

Пусть T (n) будет количеством сравнений в худшем случае в массиве из n элементов.

Следовательно,

$$T (n) = \ begin {case} 0 & if \: n = 1 \\ T (\ frac {n} {2}) + 1 & в противном случае \ end {case}$$

Используя это рекуррентное соотношение T(n)=logn$T (n) = log \: n$.

Следовательно, бинарный поиск использует O(logn)$O (log \: n)$ time.

пример

В этом примере мы собираемся найти элемент 63.