Usando rotinas de busca em C

A biblioteca padrão C oferece uma função genérica, bsearch, para realizar a busca binária de uma chave em um arranjo ordenado. O protótipo dessa rotina está definido em stdlib.h:

 void *bsearch(const void *key, const void *base, size_t nmemb,
        size_t size, int (*compar)(const void *, const void *));

A função bsearch manipula elementos de qualquer tipo especificado pelo programador. Para tanto, faz uso extensivo de ponteiros especificados genericamente no programa através do tipo void*.

A função irá procurar a chave cujo valor é apontado por key no arranjo cujo início é apontado por base. Para poder percorrer o arranjo corretamente, é preciso indicar quantos elementos estão nele contidos (nmemb) e qual o tamanho de cada elemento em bytes (size).

O programador precisa também informar como deve ser realizada a comparação entre dois elementos desse arranjo, de forma a determinar em que segmento do arranjo a busca deve continuar após cada comparação. Para tanto, o programador deve fornecer uma rotina que compare dois elementos, sendo que o primeiro será um ponteiro para a chave (key) e o segundo um ponteiro para o membro do arranjo que está sendo pesquisado. O valor de retorno dessa rotina deve ser um inteiro que será igual a 0 se os dois valores forem iguais; menor que 0 se o valor da chave for menor que o valor pesquisado; ou maior que 0 se o valor da chave for maior que o valor pesquisado no arranjo.

Por exemplo, considere a busca de um valor inteiro em um arranjo do tipo int. A função de comparação poderia ser definida como:

 int compara(int *s1, int *s2) {
   return *s1 - *s2;
 }

Por exemplo, considere que um arranjo de elementos inteiros foi definido e contém uma série de valores ordenados:

  #define SIZE 100
  ... // definição da função
   int array[SIZE];
  ... // preenchimento do arranjo

Para procurar se o arranjo contém um elemento cuja valor é 1900, a invocação seria da forma:

   int busca = 1900;
   int *found;
   found = bsearch(&busca,array,SIZE,sizeof(int),compara);
   if (found)
      printf("Encontrou %d na posicao %d\n", busca, found-array);
   else
      printf("Nao encontrou %d\n", busca);

Observe que a condição do if utiliza apenas o valor do ponteiro found -- caso seja diferente de 0, ele indica a posição de memória onde o valor foi encontrado e será interpretado como verdadeiro. Na seqüência, a expressão found-array utiliza a aritmética de ponteiros de C para apresentar a posição (o índice no arranjo) no qual o valor buscado foi encontrado -- array é o endereço-base do arranjo o qual, subtraído do endereço found, dá o número de inteiros (pois mabos são ponteiros para int) entre as duas posições.