sexta-feira, 16 de maio de 2014

[Programação em C] - Busca binária em um vetor - bsearch

Olá pessoal, nesse post iremos conhecer função bsearch que realiza uma busca binária em um vetor. Ela procura por um valor (chave de procura) em um vetor ordenado, retornando um ponteiro para a posição onde a chave de procura aparece no vetor ou NULL caso a chave não pertença ao vetor.

Iremos ver um exemplo bem simples. No exemplo a seguir o vetor já está ordenado, mas caso queira garantir que ele esteja ordenado basta utilizar a função qsort.


O código está todo comentado. Na linha 18 temos a função que compara dois elementos. É feita uma subtração dos elementos apontados por "x" e "y". Se essa subtração for negativa é porque o elemento apontado por "x" precede o elemento apontado por "y". Se a subtração for igual a 0, então é porque os dois são equivalentes. Caso a subtração seja negativa, então é porque o elemento apontado por "x" vem depois do elemento apontado por "y".

Na linha 42 é chamada a função bsearch. Ela possui cinco parâmetros: a chave, a base do vetor, a quantidade de elementos do vetor, o tamanho de cada elemento do vetor (utiliza a função sizeof) e por último a função de comparação (compare).

Se o retorno for NULL é porque o valor não foi encontrado.

Quaisquer dúvidas deixem nos comentários, até a próxima!


Nenhum comentário: