quinta-feira, 8 de outubro de 2009

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));

}

2 comentários: