La funzione bsearch () in C ++ esegue una ricerca binaria di un elemento in un array di elementi e restituisce un puntatore all'elemento se trovato.
La funzione bsearch () richiede che tutti gli elementi minori dell'elemento vengano cercati a sinistra di esso nell'array.
Allo stesso modo, tutti gli elementi più grandi dell'elemento da cercare devono trovarsi alla sua destra nell'array. Questo requisito è soddisfatto se la matrice è ordinata in ordine crescente.
bsearch () prototipo
void * bsearch (const void * key, const void * base, size_t num, size_t size, int (* compare) (const void *, const void *));
La funzione è definita nel file di intestazione.
La funzione bsearch () cerca la chiave nella base dell'array. Tutti gli elementi minori di key devono comparire prima di essa nella base dell'array. Allo stesso modo, tutti gli elementi maggiori di key devono apparire dopo di essa in base.
Per eseguire la ricerca, la funzione bsearch () effettua una serie di chiamate alla funzione indicata da compare con key come primo argomento e un elemento dell'array come secondo argomento.
Parametri bsearch ()
- chiave: puntatore all'elemento da cercare
- base: puntatore al primo elemento della matrice
- num: numero di elementi nell'array
- size: dimensione in byte di ogni elemento dell'array
- compare: un puntatore a una funzione che confronta due elementi. Ritorna
- un numero intero negativo se il primo argomento è minore del secondo
- un numero intero positivo se il primo argomento è maggiore del secondo
- zero se entrambi gli argomenti sono uguali
key viene passato come primo argomento e un elemento dell'array viene passato come secondo argomento. Il prototipo della funzione di confronto è simile a:
int compare (const void * a, const void * b);
bsearch () Restituisce il valore
La funzione bsearch () restituisce:
- Puntatore all'elemento trovato. Se vengono trovati più elementi corrispondenti, non è specificato l'indirizzo dell'elemento che la funzione restituirà come risultato.
- Puntatore nullo se l'elemento non viene trovato.
Esempio 1: come funziona la funzione 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 esegui il programma, l'output sarà:
10 trovato nella posizione 2 15 non trovato
Esempio 2: come funziona la funzione bsearch () per più di un elemento corrispondente?
#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 esegui il programma, un possibile output sarà:
14 trovato alla posizione 7
