Funktionen bsearch () i C ++ udfører en binær søgning af et element i en række elementer og returnerer en markør til elementet, hvis det findes.
Funktionen bsearch () kræver, at alle elementer, der er mindre end elementet, skal søges til venstre for det i arrayet.
Ligeledes skal alle elementer, der er større end det element, der skal søges, være til højre for det i arrayet. Dette krav er opfyldt, hvis arrayet er sorteret i stigende rækkefølge.
bsearch () prototype
ugyldig * bsearch (const ugyldig * nøgle, const ugyldig * base, størrelse_t num, størrelse_t størrelse, int (* sammenligne) (const ugyldig *, const ugyldig *));
Funktionen er defineret i header-fil.
Funktionen bsearch () søger efter nøgle i arraybasen. Alle elementer, der er mindre end nøglen, skal vises foran den i arraybasen. Ligeledes skal alle elementer, der er større end nøglen, vises efter det i basen.
For at udføre søgningen foretager funktionen bsearch () en række opkald til den funktion, der peges ved at sammenligne med nøglen som det første argument og et element fra arrayet som det andet argument.
bsearch () Parametre
- nøgle: Markør til det element, der skal søges
- base: Markør til det første element i arrayet
- num: Antal element i arrayet
- størrelse: Størrelse i byte for hvert element i arrayet
- sammenligne: En markør til en funktion, der sammenligner to elementer. Det vender tilbage
- et negativt heltal, hvis det første argument er mindre end det andet
- et positivt heltal, hvis det første argument er større end det andet
- nul, hvis begge argumenter er ens
nøglen sendes som det første argument, og et element fra arrayet sendes som det andet argument. Prototypen for sammenligningsfunktionen ser ud som:
int sammenligne (const void * a, const void * b);
bsearch () Returværdi
Funktionen bsearch () returnerer:
- Markør til det fundne element. Hvis der findes mere end et matchende element, er det ikke specificeret, hvilket elements adresse funktionen returnerer som resultatet.
- Null markør, hvis elementet ikke findes.
Eksempel 1: Hvordan fungerer bsearch () -funktionen?
#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 kører programmet, vil output være:
10 fundet ved position 2 15 ikke fundet
Eksempel 2: Hvordan fungerer bsearch () -funktionen til mere end et matchende 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 kører programmet, vil en mulig output være:
14 fundet ved position 7
