Descrição Indutiva: Busca Binária recursiva em Java

Neste post, vamos descrever indutivamente e discutir a complexidade da busca binária. Como veremos,    a busca binária é mais eficiente que a busca sequencial discutida no post Descrição indutiva: Busca sequencial recursiva em Java. No entanto, para que possamos aplicar a busca binária em um vetor (lista) é necessário que ele esteja ordenado.

Descrição Indutiva:

• Caso Base: Para um vetor com apenas um elemento, basta verificar se o elemento procurado é o elemento armazenado no vetor.
• Hipótese de Indução: Vamos assumir que a hipótese de indução sabe procurar o elemento desejado em um vetor com $\frac{n}{2}$ elementos.
• Caso Geral: Vamos procurar um elemento K no vetor. Para compor o caso geral, vamos dividir o vetor ao meio e verificar se o elemento central é maior ou menor que K. Caso o elemento central seja menor que K, então K poderá ser encontrado na segunda parte do vetor, caso contrário, o elemento K poderá ser encontrado na primeira parte do vetor.

A implementação em Java (ou em sua linguagem predileta) segue exatamente a descrição indutiva do problema.

• Implementação em Java

public class BinarySearch {

  public static int binarySearch(int vet[], int value, int left, int rigth) {
    int middle;
    if (left <= rigth) {
      middle = left + (rigth - left) / 2;
      if (vet[middle] == value)
      return middle;
    else if (vet[middle] > value)
      return binarySearch(vet, value, left, middle - 1);
    else
      return binarySearch(vet, value, middle + 1, rigth);
    }
    return -1;
}
  public static void main(String[] args) {
    int vet[] = { 1, 3, 4, 6, 78, 90 };
    System.out.println(binarySearch(vet, 3, 0, 5));
  }
}

Complexidade
A busca binária é muito eficiente, pois a cada passo descarta a metade do espaço de busca. A relação de recorrência que expressa a complexidade do algoritmo é: $T(n) = T(\frac{n}{2}) + 1$. Resolvendo a recorrência temos que a busca binária é O(log n).


Gostou da publicação? Sim? Então curta nossa fan page no Facebook e acompanhe nossas postagens.

@inductioncode