Pesquisa binária

Origem: Wikipédia, a enciclopédia livre.

A pesquisa ou busca binária ( em inglês binary search algorithm ou binary chop ) é um algoritmo de busca em vetores que requer acesso aleatório aos elementos do mesmo. 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. A complexidade desse algoritmo é da ordem de log₂ n, onde n é o tamanho do vetor de busca.

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[], inicio, fim, e}
     i recebe o índice no meio de inicio e fim
     se V[i] é igual a e
          então devolva o índice i    # encontrei e
          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)

[editar] Código em C

int PesquisaBinaria(char chave,char k[],int N)
{
     int inf,sup,meio;
     inf=0;
     sup=N-1;
     while (inf<=sup) {
          meio=(inf+sup)/2;
          if (chave==k[meio])
               return meio;
          else if (chave<k[meio])
               sup=meio-1;
          else
               inf=meio+1;
     }
     return -1;   /* não encontrado */
}

[editar] Código em Java

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

[editar] Código em C#

private int pesquisaBinaria(int[] vetor, int inicio, int fim, int valorPesquisa)
        {
            
            int idxPivo = (inicio + fim) / 2;

            if (valorPesquisa != vetor[idxPivo])
            {
                if (valorPesquisa < vetor[idxPivo])
                {
                    idxPivo  = PesquisaBinaria(vetor, inicio, idxPivo, valorPesquisa);
                }
                else
                {
                    idxPivo  = PesquisaBinaria(vetor, idxPivo, fim, valorPesquisa);
                }
            }

            return idxPivo ;               //retorna o indice da matriz em que contêm o
                                           //o valor de entrada a ser pesquisado
        }

[editar] 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}
            repeat
               meio := (inicio+fim) div 2;
                 if (Chave = vetor[meio]) then 
                      BuscaBinaria := meio;
                 if (Chave < vetor[meio]) then 
                      fim:=(meio-1); 
                 if (Chave > vetor[meio]) then
                      inicio:=(meio+1);
          until (Chave = Vetor[meio]) or (inicio > fim);
            if (Chave = Vetor[meio]) then 
                BuscaBinaria := meio 
            else 
                BuscaBinaria := -1; {Retorna o valor encontrado, ou -1 se a chave nao foi encontrada.}
     end;

[editar] Java

public int achar(long chave)
{
 int limiteInf = 0;
 int limiteSup = nElems-1;
 int curIn;
   while(true)
   {
     curIn = (limiteInf + limiteSup ) / 2;
      if(a[curIn]==chave)
       return curIn;
      else 
        if(limiteInf > limiteSup)
         return nElems;
        else
        {
         if(a[curIn] < chave)
          limiteInf = curIn + 1;
         else
          limiteSup = curIn - 1;
        } // fim o else que divide a faixa
   } // fim do while
} // fim do metodo achar()