Funkcija bsearch (), kas atrodas C ++, veic elementa masīvā elementa bināro meklēšanu un atgriež rādītāju elementam, ja tāds ir atrasts.
Funkcijai bsearch () ir nepieciešams, lai visi elementi, kas ir mazāki par elementu, tiktu meklēti masīvā pa kreisi no tā.
Tāpat visiem masīva elementiem, kas ir lielāki par meklējamo elementu, jābūt pa labi no tā. Šī prasība ir izpildīta, ja masīvs ir sakārtots augošā secībā.
bsearch () prototips
void * bsearch (const void * atslēga, const void * bāze, size_t num, size_t size, int (* salīdzināt) (const void *, const void *));
Funkcija ir definēta galvenes failā.
Funkcija bsearch () meklē atslēgu masīva bāzē. Visiem elementiem, kas mazāki par atslēgu, pirms tā ir jāparādās masīva bāzē. Tāpat visiem elementiem, kas ir lielāki par atslēgu, ir jāparādās aiz tā bāzē.
Lai veiktu meklēšanu, funkcija bsearch () veic virkni izsaukumu uz funkciju, kuru norāda salīdzināt ar atslēgu kā pirmo argumentu un elementu no masīva kā otro argumentu.
bsearch () parametri
- atslēga: rādītājs uz meklējamo elementu
- bāze: masīva pirmā elementa rādītājs
- num: masīva elementa numurs
- lielums: katra masīva elementa lielums baitos
- salīdzināt: rādītājs funkcijai, kas salīdzina divus elementus. Tas atgriežas
- negatīvs vesels skaitlis, ja pirmais arguments ir mazāks par otro
- pozitīvs vesels skaitlis, ja pirmais arguments ir lielāks par otro
- nulle, ja abi argumenti ir vienādi
atslēga tiek nodota kā pirmais arguments un masīva elements tiek nodots kā otrais arguments. Salīdzināšanas funkcijas prototips izskatās šādi:
int salīdzināt (const void * a, const void * b);
bsearch () Atgriešanās vērtība
Funkcija bsearch () atgriež:
- Rādītāja atrastajam elementam. Ja tiek atrasti vairāki atbilstoši elementi, tad nav norādīts, kura elementa adresi funkcija atgriezīs kā rezultātu.
- Null rādītājs, ja elements nav atrasts.
1. piemērs: Kā darbojas funkcija 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; )
Palaidot programmu, izeja būs:
10 atrasts 2. pozīcijā 15 nav atrasts
2. piemērs: Kā funkcija bsearch () darbojas vairāk nekā vienam atbilstošam elementam?
#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; )
Palaidot programmu, iespējamā izeja būs:
14 atrasts 7. pozīcijā
