Pesquisa binária

Pesquisa binária
classe	Algoritmo de busca
estrutura de dados	Array, Listas ligadas
complexidade caso médio	${O}(\log n)$
complexidade melhor caso	${O}(1)$
complexidade de espaços pior caso	${O}(\log n)$
otimo	Sim
espaço	${O}(1)$
Algoritmos

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 Θ(log₂ n), em que n é o tamanho do vetor de busca. Apresenta-se mais eficiente que a Busca linear cuja ordem é O(n).

Pseudo-Código

Um pseudo-código recursivo para esse algoritmo, dados V o vetor com elementos comparáveis, n seu tamanho 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

Implementações

Código em Ruby

def search(vector, lower, upper, element)
   return -1 if lower > upper
   mid = (lower+upper)/2
   if (vector[mid] == element)
     element
   elsif (element < vector[mid])
     search(vector, lower, mid-1, element)
   else
     search(vector, mid+1, upper, element)
   end
end
 
def binary_search(vector,element)
  search(vector, 0, vector.size-1, element)
end

Código em C

//em C para se passar um vetor como parâmetro para uma função, tem que se passar o ponteiro do vetor
int PesquisaBinaria ( int *array, int chave , int N)
{
     int inf = 0; //Limite inferior      (o primeiro elemento do vetor em C é zero          )
     int sup = N-1; //Limite superior    (termina em um número a menos 0 à 9 são 10 numeros )
     int meio;
     while (inf <= sup) 
     {
          meio = inf + (sup-inf)/2;
          if (chave == array[meio])
               return meio;
          else if (chave < array[meio])
               sup = meio-1;
          else
               inf = meio+1;
     }
     return -1;   // não encontrado
}

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

Java

public static int buscaBinaria( int[] array, int valor )
{
        int esq = 0;
        int dir = array.length - 1;
        int valorMeio;
 
        while ( esq <= dir ) {
                valorMeio = esq + ((dir - esq) / 2);
                if ( array[valorMeio] < valor ) {
                        esq = valorMeio + 1;
                } else if( array[valorMeio] > valor ) {
                        dir = valorMeio - 1;
                } else {
                        return valorMeio;
                }
        }
        return -1;
}

Código em python

def binsearch(seq, search):    
   right = len(seq)
   left = 0
   previous_center = -1
   if search < seq[0]:
       return -1
   while 1:
       center = (left + right) / 2
       candidate = seq[center]
       if search == candidate:
           return center
       if center == previous_center:
           return - 2 - center
       elif search < candidate:
           right = center
       else:
           left = center
       previous_center = center

Código em C#

static int pesquisaBinaria(int[] vetor, int chave)
    {
    //Ordena o vetor.
    Array.Sort(vetor);
 
    int meio;
    int Min = 0;
    int Max = vetor.Length - 1;
 
    do
        {
        meio = (int)(Min + Max) / 2;
        if (vetor[meio] == chave)
            {
            //Retorna a posição do número na seqüencia.
            return meio;
            }
        else if (chave > vetor[meio])
            Min = meio + 1;
        else
            Max = meio - 1;
        }
    while (Min <= Max);
 
    //Caso o retorno for -1, então o número não existe na seqüencia.
    return -1;
    }

Código em Pascal

     function BuscaBinaria (Vetor: array of string; Chave: string; Dim: integer): integer;
          var inicio, fim: integer; {Auxiliares que representam o inicio e o fim do vetor analisado}
              meio: integer; {Meio do vetor}
     begin
          fim := Dim; {O valor do último índice do vetor}
          inicio := 1; {O valor do primeiro índice do vetor}
          BuscaBinaria := -1; {Retorna o valor -1 se a chave nao for encontrada.}
            repeat
                 meio := (inicio+fim) div 2;
                 if (Chave = vetor[meio]) then
                 begin
                      BuscaBinaria := meio;
                      inicio:=fim+1; {Interrompo o repeat quando a chave for encontrada sem ter que testar lá no until. Bonito não?!}
                 end;
                 if (Chave < vetor[meio]) then 
                      fim:=(meio-1); 
                 if (Chave > vetor[meio]) then
                      inicio:=(meio+1);
            until (inicio > fim);
      end;

Código Recursivo em Pascal

    function BuscaBinariaRecursiva(var Vetor: array of string; L,H: integer; chave: string): integer;
       var m:integer;    {variavel auxiliar que indica o meio do vetor}
    begin
      ordena(Vetor,H);    {Procedimento que ordena o vetor, tais como: bubble sort, quick sort, entre outros}
      if L>H then         {L= variavel que indica o começo do vetor, H= variavel que indica o fim do vetor}
        BuscaBinariaRecursiva:=-1
      else
       begin
         m:=(L+H) div 2;
      if x<Vetor[M] then
         BuscaBinariaRecursiva:=BuscaBinariaRecursiva(Vetor,L,M-1,x)
     else
       if x>Vetor[M] then
         BuscaBinariaRecursiva:=BuscaBinariaRecursiva(Vetor,M+1,H,x)
       else
         BuscaBinariaRecursiva:=M;
   end;
end;

Código em Lua

function buscaBinaria(v, x)
        ini = 1
        fim = #v
        while(ini<=fim)
        do
                pivo= math.floor((fim+ini)/2)
                if(x > v[pivo])
                then
                        ini = pivo+1
                end
 
                if(x < v[pivo])
                then
                        fim = pivo-1
                end
 
                if (x==v[pivo])
                then
                        return pivo
                end
        end
        return -1
end

Código em Scheme

    (define  vetor (vector 1 2 4 6 8 9 10 23 45 ))
    (define (buscab vetor numero inicio fim)
      (letrec  ([ndivi (floor (/ (+ fim inicio) 2))] [n-medio (vector-ref vetor ndivi)])
        (cond
             [(> inicio fim) false]
             [(= numero n-medio) ndivi]
             [(< numero n-medio) (buscab vetor numero inicio (- ndivi 1))]
             [else (> numero n-medio) (buscab vetor numero (+ ndivi 1) fim)])))
    (buscab vetor 23 0 9)

Código em PHP

function buscaBinaria($valorPesquisa, array $vetor) {
 
        $n_elementos = count($vetor);
        $inicio = 0; $fim = $n_elementos -1; $meio = (int) (($fim - $inicio) / 2) + $inicio;
 
        while ($inicio <= $fim) {
                if ($vetor[$meio] < $valorPesquisa) {
                        $inicio = $meio + 1;
                } elseif ($vetor[$meio] > $valorPesquisa) {
                        $fim = $meio - 1;
                } else {
                        return $meio;
                }
 
                $meio = (int) (($fim - $inicio) / 2) + $inicio;
 
        }
 
        return -1;
}
 
$a = array(1, 2, 3, 4, 5, 6);
 
print "call buscaBinaria(4, [1, 2, 3, 4, 5, 6]); return: "; var_dump(buscaBinaria(4, $a));
print "call buscaBinaria(6, [1, 2, 3, 4, 5, 6]); return: "; var_dump(buscaBinaria(6, $a));
print "call buscaBinaria(1, [1, 2, 3, 4, 5, 6]); return: "; var_dump(buscaBinaria(1, $a));
print "call buscaBinaria(8, [1, 2, 3, 4, 5, 6]); return: "; var_dump(buscaBinaria(8, $a));

Ligações externas

• Tecnologia da Informação - Goiânia - GO
• 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.
• Explanação e código da busca binária em C++
• Google Research: Nearly All Binary Searches and Mergesorts are Broken