DAA - Pesquisa Binária

Neste capítulo, discutiremos outro algoritmo baseado no método de divisão e conquista.

Declaração do Problema

A pesquisa binária pode ser realizada em uma matriz classificada. Nesta abordagem, o índice de um elementoxé determinado se o elemento pertence à lista de elementos. Se a matriz não estiver classificada, a pesquisa linear será usada para determinar a posição.

Solução

Neste algoritmo, queremos descobrir se o elemento x pertence a um conjunto de números armazenados em uma matriz numbers[]. Ondel e r representam o índice esquerdo e direito de uma submatriz na qual a operação de pesquisa deve ser realizada.

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)

Análise

A pesquisa linear é executada em O(n)Tempo. Enquanto a pesquisa binária produz o resultado emO(log n) Tempo

Deixei T(n) ser o número de comparações no pior caso em uma matriz de n elementos

Conseqüentemente,

$$ T (n) = \ begin {cases} 0 & if \: n = 1 \\ T (\ frac {n} {2}) + 1 & caso contrário \ end {cases} $$

Usando esta relação de recorrência $ T (n) = log \: n $.

Portanto, a pesquisa binária usa $ O (log \: n) $ tempo.

Exemplo

Neste exemplo, vamos pesquisar o elemento 63.