Pesquisa binária

Pesquisa binária
classe	Algoritmo de busca
estrutura de dados	Array
complexidade caso médio	${\displaystyle {O}(\log n)}$
complexidade melhor caso	${\displaystyle {O}(1)}$
complexidade de espaços pior caso	${\displaystyle {O}(\log n)}$
otimo	Sim
espaço	${\displaystyle {O}(1)}$
Algoritmos
Esta caixa: ver discutir

A pesquisa ou busca binária (em inglês binary search algorithm ou binary chop) é um algoritmo de busca em vetores que segue o paradigma de divisão e conquista. Ela parte do pressuposto de que o vetor está ordenado e realiza sucessivas divisões do espaço de busca comparando o elemento buscado (chave) com o elemento no meio do vetor. Se o elemento do meio do vetor for a chave, a busca termina com sucesso. Caso contrário, se o elemento do meio vier antes do elemento buscado, então a busca continua na metade posterior do vetor. E finalmente, se o elemento do meio vier depois da chave, a busca continua na metade anterior do vetor.

Análise de Complexidade

A complexidade desse algoritmo é da ordem de ${\displaystyle \Theta (\log _{2}n)}$^[1], em que ${\displaystyle n}$ é o tamanho do vetor de busca. Apresenta-se mais eficiente que a Busca linear cuja ordem é ${\displaystyle O(n)}$^[2].

Procedimento

Dado uma lista ${\displaystyle A}$ de ${\displaystyle n}$ elementos com os valores ${\displaystyle A_{0}}$, ${\displaystyle A_{1}}$, ${\displaystyle A_{2}}$, ${\displaystyle ...}$, ${\displaystyle A_{n-1}}$ordenada de tal modo que ${\displaystyle A_{0}\leq A_{1}\leq A_{2}\leq ...\leq A_{n-1}}$, e um valor para pesquisa ${\displaystyle T}$, a seguinte rotina usa pesquisa binária para achar o índice de ${\displaystyle T}$ em ${\displaystyle A}$.

1. Defina ${\displaystyle L}$ para 0 e ${\displaystyle R}$ para ${\displaystyle n-1}$
2. Se ${\displaystyle L>R}$ a pesquisa termina sem sucesso
3. Defina ${\displaystyle m}$(o índice do meio da lista) para ${\displaystyle {\frac {L+R}{2}}}$ arredondado
4. Se ${\displaystyle A_{m}<T}$, defina ${\displaystyle L}$ para ${\displaystyle m+1}$ e volte ao segundo passo
5. Se ${\displaystyle A_{m}>T}$, defina ${\displaystyle R}$ para ${\displaystyle m-1}$ e volte ao segundo passo.
6. Se ${\displaystyle A_{m}=T}$, a pesquisa está feita, o índice de ${\displaystyle T}$ é ${\displaystyle m}$

Implementações

Pseudo-Código

Um pseudo-código recursivo para esse algoritmo, dados V o vetor com elementos comparáveis e e o elemento que se deseja encontrar:

BUSCA-BINÁRIA(V[], início, fim, e)
    i recebe o índice do meio entre início e fim
    se (v[i] = e) entao
        devolva o índice i   # elemento e encontrado
    fimse
    se (inicio = fim) entao
        não encontrou o elemento procurado
    senão
       se (V[i] vem antes de e) então
          faça a BUSCA-BINÁRIA(V, i+1, fim, e)
       senão
          faça a BUSCA-BINÁRIA(V, inicio, i-1, e)
       fimse
    fimse

Código em C

//Implementação Iterativa:

int PesquisaBinaria (int vet[], int chave, int Tam)
{
     int inf = 0;     // limite inferior (o primeiro índice de vetor em C é zero          )
     int sup = Tam-1; // limite superior (termina em um número a menos. 0 a 9 são 10 números)
     int meio;
     while (inf <= sup)
     {
          meio = (inf + sup)/2;
          if (chave == vet[meio])
               return meio;
          if (chave < vet[meio])
               sup = meio-1;
          else
               inf = meio+1;
     }
     return -1;   // não encontrado
}

//Implementação Recursiva:

// x => chave | v[] => vetor ordenado | e => limite inferior (esquerda) | d => limite superior (direita)
int PesquisaBinaria (int x, int v[], int e, int d)
{
 int meio = (e + d)/2;
 if (v[meio] == x)
    return meio;
 if (e >= d)
    return -1; // não encontrado
 else
     if (v[meio] < x)
        return PesquisaBinaria(x, v, meio+1,      d);
     else
        return PesquisaBinaria(x, v,      e, meio-1);
}

Obs: A linguagem C fornece a função bsearch^[3] na sua biblioteca padrão.

Ver também

• Busca linear

Referências

Ligações externas

• Projeto de Algoritmos - Paulo Feofiloff -IME-USP
• NIST Dicionário de Algoritmos e Estrutura de Dados :binary search
• Tim Bray. On the Goodness of Binary Search. Pequeno ensaio das vantagens da busca binária e exemplo de código em Java.
• Google Research: Nearly All Binary Searches and Mergesorts are Broken
• Busca binária em Java e em C

• Portal das tecnologias de informação