A função bsearch () em C ++ executa uma pesquisa binária de um elemento em uma matriz de elementos e retorna um ponteiro para o elemento se encontrado.
A função bsearch () requer que todos os elementos menos do que o elemento a ser pesquisado à esquerda dele na matriz.
Da mesma forma, todos os elementos maiores que o elemento a ser pesquisado devem estar à direita dele na matriz. Esse requisito é atendido se a matriz for classificada em ordem crescente.
protótipo bsearch ()
void * bsearch (const void * chave, const void * base, size_t num, size_t size, int (* compare) (const void *, const void *));
A função é definida no arquivo de cabeçalho.
A função bsearch () procura a chave na base do array. Todos os elementos menores que a chave devem aparecer antes dele na base da matriz. Da mesma forma, todos os elementos maiores que a chave devem aparecer depois dele na base.
Para realizar a pesquisa, a função bsearch () faz uma série de chamadas para a função apontada por compare with key como o primeiro argumento e um elemento da matriz como o segundo argumento.
Parâmetros bsearch ()
- chave: ponteiro para o elemento a pesquisar
- base: ponteiro para o primeiro elemento da matriz
- num: número do elemento na matriz
- size: tamanho em bytes de cada elemento na matriz
- compare: um ponteiro para uma função que compara dois elementos. Retorna
- um número inteiro negativo se o primeiro argumento for menor que o segundo
- um número inteiro positivo se o primeiro argumento for maior que o segundo
- zero se ambos os argumentos forem iguais
a chave é passada como o primeiro argumento e um elemento da matriz é passado como o segundo argumento. O protótipo da função de comparação se parece com:
int compare (const void * a, const void * b);
bsearch () Valor de retorno
A função bsearch () retorna:
- Ponteiro para o elemento encontrado. Se mais de um elemento correspondente for encontrado, não será especificado qual endereço do elemento a função retornará como resultado.
- Ponteiro nulo se o elemento não for encontrado.
Exemplo 1: Como funciona a função bsearch ()?
#include #include using namespace std; int compare(const void* a, const void* b) ( const int* x = (int*) a; const int* y = (int*) b; return (*x - *y); ) int main() ( const int num = 10; int arr(num) = (5,9,10,14,16,19,21,26,29,31); int key1 = 10; int *p1 = (int*)bsearch(&key1,arr,num,sizeof(int),compare); if(p1 == NULL) cout << key1 << " not found " << endl; else cout << key1 << " found at position " << (p1-arr) << endl; int key2 = 15; int *p2 = (int*)bsearch(&key2,arr,num,sizeof(int),compare); if(p2 == NULL) cout << key2 << " not found " << endl; else cout << key2 << " found at position " << (p2-arr) << endl; return 0; )
Quando você executa o programa, a saída será:
10 encontrado na posição 2 15 não encontrado
Exemplo 2: Como a função bsearch () funciona para mais de um elemento correspondente?
#include #include using namespace std; int compare(const void* a, const void* b) ( const int* x = (int*) a; const int* y = (int*) b; return (*x - *y); ) int main() ( const int num = 10; int arr(num) = (2,3,5,7,8,10,14,14,14,15); int key = 14; int *p = (int*)bsearch(&key,arr,num,sizeof(int),compare); if(p == NULL) cout << key << " not found " << endl; else /* 14 occurs at position 6,7 and 8*/ cout << key << " found at position " << (p-arr) << endl; return 0; )
Quando você executa o programa, uma possível saída será:
14 encontrado na posição 7
