Pesquisa Binária

Considere o seguinte problema encontrar o indíce do elemento chave de um vetor ordenado, onde elemento chave é um valor inteiro a ser buscado no vetor/array.

A forma mais intuitiva seria realizar uma busca sequencial percorrendo o vetor da esquerda para direita verificando se o valor buscado foi encontrado. Porém, utilizando essa estratégia, no pior caso (o item buscado não existe no vetor), o algoritmo irá verificar o valor realizando n (n é o tamanho do vetor de busca) iterações ou apresentado uma complexidade de O(n). Esse algoritmo de busca não é muito eficiente para resolver esse problema. Considerando que o vetor está ordenado podemos implementar um algoritmo mais eficiente do que o de busca sequencial. O algoritmo otimizado é conhecido como busca binária.

O algoritmo de busca binária utiliza o paradigma Dividir para Conquistar, essa estratégia consiste em dividir um problema em problemas menores. Em nosso problema seria dividir pela metade o espaço de busca à cada iteração.

A pesquisa binária inicia a verificação do valor no meio do vetor, vamos supor que o valor buscado é menor do que valor do meio do array, então é criado um novo espaço de busca no qual o valor poderá ser encontrado, em nosso exemplo o espaço de busca será a esquerda do meio do vetor. Supondo que agora o valor encontrado na busca seja menor do que o valor procurado, como o valor buscado é posterior ao valor obtido, logo o novo espaço de busca estará a direita do valor verificado. Considerando que na próxima busca ao iniciar a verificação o valor verificado é igual ao buscado, então o valor foi encontrado no vetor.

O algoritmo de busca binária utiliza a estratégia de reduzir o espaço de busca pela metade até o momento em que tem a possilidade de encontrar o valor no vetor ordenado. Dessa forma, o algoritmo irá realizar, no pior caso, log n iterações para verificar se existe o valor no vetor ou executando numa complexidade O(log n).

A seguir o algoritmo de busca binária é detalhado numa linguagem de programação:

   /**
    * Busca iterativamente o item dentro do vetor vector. A cada iteração
    * reduz o espaço de busca pela metade. Ao encontrar o item retorna seu índice. Caso contrário retorna -1
    * 
    * @param chave    - Número que será pesquisado.
    * @param numeros - Vetor ordenado de números.
   */
  public int pesquisaBinaria(int chave, int[] numeros) {
    int inicio = 0;         
    int meio = 0;         
    int fim = numeros.length - 1;
    
    while(inicio <= fim) { // Condição de parada
      meio = (fim + inicio)/2; // Calcula o meio do sub-vetor
      
      System.out.println("Inicio: " + numeros[inicio] + " - Meio: " + numeros[meio] + " - Fim: " + numeros[fim]);
      System.out.println("Inicio: " + inicio + " - Meio: " + meio + " - Fim: " + fim);
      
      if(numeros[meio] == chave) { // Item encontrado
        System.out.println("Encontrou o número " + chave);
        return meio;
      }
      
      // Este if serve para diminuir o tamanho do vetor pela metade. 
      if(numeros[meio] < chave) { // Item está no sub-vetor à direita
        inicio = meio + 1;
      } else {
        fim = meio - 1; // vector[i] > item. Item está no sub-vetor à esquerda
      }
    }
    
    if(inicio > fim) {
      System.out.println("Não encontrou o número " + chave);
    }
    
    return -1;
  }