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 {cases} 0 & если \: n = 1 \\ T (\ frac {n} {2}) + 1 & в противном случае \ end {ases} $$

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

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

пример

В этом примере мы будем искать элемент 63.