Funksjonen bsearch () i C ++ utfører et binært søk av et element i en rekke elementer og returnerer en peker til elementet hvis det blir funnet.
Funksjonen bsearch () krever at alle elementer som er mindre enn elementet, skal søkes til venstre for det i matrisen.
På samme måte må alle elementene som er større enn elementet som skal søkes, være til høyre for det i matrisen. Dette kravet oppfylles hvis matrisen er sortert i stigende rekkefølge.
bsearch () prototype
void * bsearch (const void * key, const void * base, size_t num, size_t size, int (* jämför) (const void *, const void *));
Funksjonen er definert i topptekstfilen.
Funksjonen bsearch () søker etter nøkkel i matrixbasen. Alle elementer mindre enn nøkkel må vises foran den i matrixbasen. Likeledes må alle elementer som er større enn nøkkelen vises etter det i basen.
For å utføre søket, gjør bsearch () -funksjonen en serie anrop til funksjonen pekt ved å sammenligne med nøkkel som det første argumentet og et element fra matrisen som det andre argumentet.
bsearch () Parametere
- nøkkel: Peker til elementet du vil søke
- base: peker til det første elementet i matrisen
- num: Antall elementer i matrisen
- størrelse: Størrelse i byte for hvert element i matrisen
- sammenligne: En peker til en funksjon som sammenligner to elementer. Det kommer tilbake
- et negativt heltall hvis det første argumentet er mindre enn det andre
- et positivt heltall hvis det første argumentet er større enn det andre
- null hvis begge argumentene er like
nøkkel sendes som det første argumentet, og et element fra matrisen sendes som det andre argumentet. Prototypen til sammenligningsfunksjonen ser ut som:
int sammenligne (const void * a, const void * b);
bsearch () Returverdi
Funksjonen bsearch () returnerer:
- Peker til funnet element. Hvis mer enn ett samsvarende element blir funnet, er det uspesifisert hvilket element adresse funksjonen vil returnere som resultat.
- Nullpeker hvis elementet ikke er funnet.
Eksempel 1: Hvordan fungerer bsearch () -funksjonen?
#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; )
Når du kjører programmet, vil utdataene være:
10 funnet på posisjon 2 15 ikke funnet
Eksempel 2: Hvordan fungerer bsearch () -funksjonen for mer enn ett samsvarende element?
#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; )
Når du kjører programmet, vil en mulig utgang være:
14 funnet ved posisjon 7