De functie bsearch () in C ++ voert een binaire zoekopdracht uit naar een element in een array van elementen en retourneert een pointer naar het element indien gevonden.
De functie bsearch () vereist dat alle elementen minder dan het element links ervan in de array worden doorzocht.
Evenzo moeten alle elementen die groter zijn dan het element dat moet worden doorzocht, rechts ervan in de array staan. Aan deze vereiste is voldaan als de array in oplopende volgorde is gesorteerd.
bsearch () prototype
void * bsearch (const void * key, const void * base, size_t num, size_t size, int (* vergelijk) (const void *, const void *));
De functie is gedefinieerd in het header-bestand.
De functie bsearch () zoekt naar sleutel in de matrixbasis. Alle elementen kleiner dan de sleutel moeten ervoor in de matrixbasis verschijnen. Evenzo moeten alle elementen groter dan de sleutel erachter in de basis verschijnen.
Om de zoekopdracht uit te voeren, voert de functie bsearch () een reeks aanroepen uit naar de functie die wordt aangewezen door te vergelijken met key als het eerste argument en een element uit de array als het tweede argument.
bsearch () Parameters
- key: Pointer naar het element om te zoeken
- base: Pointer naar het eerste element van de array
- num: nummer van het element in de array
- size: grootte in bytes van elk element in de array
- vergelijk: een aanwijzer naar een functie die twee elementen vergelijkt. Het keert terug
- een negatief geheel getal als het eerste argument kleiner is dan het tweede
- een positief geheel getal als het eerste argument groter is dan het tweede
- nul als beide argumenten gelijk zijn
key wordt doorgegeven als het eerste argument en een element uit de array wordt doorgegeven als het tweede argument. Het prototype van de vergelijkingsfunctie ziet er als volgt uit:
int vergelijken (const void * a, const void * b);
bsearch () Retourwaarde
De functie bsearch () retourneert:
- Pointer naar het gevonden element. Als er meer dan één overeenkomend element wordt gevonden, is het niet gespecificeerd welk adres van het element de functie als resultaat zal retourneren.
- Null-pointer als het element niet wordt gevonden.
Voorbeeld 1: Hoe werkt de functie 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; )
Wanneer u het programma uitvoert, is de uitvoer:
10 gevonden op positie 2 15 niet gevonden
Voorbeeld 2: Hoe werkt de functie bsearch () voor meer dan één overeenkomende elementen?
#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; )
Wanneer u het programma uitvoert, is een mogelijke uitvoer:
14 gevonden op positie 7
