Pesquisa binária em vetor ordenado

A pesquisa ou busca binária é um algoritmo de pesquisa em vetores bastante eficiente. Aplicando somente quando o vetor está ordenado, o algoritmo realiza sucessivas divisões no espaço de pesquisa comparando o elemento procurado com o elemento do meio do vetor.

Se o elemento do meio do vetor for igual ao elemento procurado, a pesquisa termina com sucesso retornando a posição do elemento. Caso contrário, se o elemento do meio vier antes do elemento procurado, então repete-se a pesquisa para a metade posterior ao meio do vetor. E se o elemento do meio vier depois do elemento procurado, repete-se a pesquisa para a metade anterior ao meio do vetor.

No exemplo de código a seguir, em linguagem C, é apresentado duas versões do algoritmo, uma função com a versão iterativa e outra função com a versão recursiva. Quando o elemento procurado não for encontrado é retornado o valor -1.

A variável esq armazena a primeira posição mais à esquerda, o início do vetor do espaço de pesquisa e, do mesmo modo, a variável dir armazena a última posição mais à direita, o fim do vetor do espaço de pesquisa. Acompanhe o código:

#include <stdio.h>
#include <stdlib.h>

int pesqbit(int *vetor, int tamanho, int valor) { // versão iterativa.

 int esq = 0;
 int dir = tamanho - 1;
 int meio;

 while (esq <= dir) {
 
   meio = (esq + dir)/2;
 
   if (vetor[meio] == valor) {
     return meio;
   } else if ((vetor[meio] < valor) && (esq < dir)) {
     esq = meio + 1;
   } else if ((vetor[meio] > valor) && (esq < meio)) {
     dir = meio - 1;
   } else {
     return -1;
   }
 }

}

int pesqbre(int *vetor, int esq, int dir, int valor) { // versão recursiva.

 int meio = (esq + dir)/2;

 if (vetor[meio] == valor) {
   return meio;
 } else if ((vetor[meio] < valor) && (esq < dir)) {
   return pesqbre(vetor, meio+1, dir, valor);
 } else if ((vetor[meio] > valor) && (esq < meio)) {
   return pesqbre(vetor, esq, meio-1, valor);
 } else {
   return -1;
 }

}

int main() { // exemplo de uso com as chamadas para as funções.

 int valor;
 int vetor[] = {1,2,3,4,5,6,7,8,9,10,11,12};

 printf("Digite um numero: ");
 scanf("%d", &valor);

 printf("(Versao Iterativa) A posicao e: %d\n", pesqbit(vetor, sizeof vetor / sizeof (int), valor));
 printf("(Versao Recursiva) A posicao e: %d\n\n", pesqbre(vetor, 0, (sizeof vetor / sizeof (int))-1, valor));

}