Funkcia bsearch () v C ++ vykonáva binárne vyhľadávanie prvku v rade prvkov a vráti ukazovateľ na prvok, ak je nájdený.
Funkcia bsearch () vyžaduje, aby sa v poli vľavo od neho hľadali všetky prvky menšie ako prvok.
Rovnako tak všetky prvky väčšie ako hľadaný prvok musia byť v poli napravo od neho. Táto požiadavka je splnená, ak je pole zoradené vzostupne.
prototyp bsearch ()
void * bsearch (const void * kľúč, const void * základňa, size_t počet, veľkosť_t veľkosť, int (* porovnanie) (const void *, const void *));
Funkcia je definovaná v hlavičkovom súbore.
Funkcia bsearch () hľadá kľúč v základni poľa. Pred ním sa v základni poľa musia nachádzať všetky prvky s menej ako kľúčom. Rovnako sa za ním v základni musia objaviť všetky prvky väčšie ako kľúč.
Aby bolo možné vykonať vyhľadávanie, funkcia bsearch () uskutoční sériu hovorov na funkciu, na ktorú odkazuje porovnanie s kľúčom ako prvým argumentom a prvkom z poľa ako druhým argumentom.
bsearch () parametre
- kľúč: Ukazovateľ na prvok, ktorý sa má vyhľadať
- base: Ukazovateľ na prvý prvok poľa
- num: Počet prvkov v poli
- size: Veľkosť každého prvku v poli v bajtoch
- porovnanie: Ukazovateľ na funkciu, ktorá porovnáva dva prvky. Vracia sa to
- záporné celé číslo, ak je prvý argument menší ako druhý
- kladné celé číslo, ak je prvý argument väčší ako druhý
- nula, ak sú obidva argumenty rovnaké
ako prvý argument sa odovzdá kľúč a ako druhý argument sa odovzdá prvok z poľa. Prototyp porovnávacej funkcie vyzerá takto:
int porovnaj (const void * a, const void * b);
bsearch () Vrátiť hodnotu
Vráti funkcia bsearch ():
- Ukazovateľ na nájdený prvok. Ak sa nájde viac ako jeden zodpovedajúci prvok, potom nie je určené, ktorá adresa prvku bude funkciou vrátená ako výsledok.
- Nulový ukazovateľ, ak sa prvok nenájde.
Príklad 1: Ako funguje funkcia 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; )
Po spustení programu bude výstup:
10 nájdené na pozícii 2 15 nenájdené
Príklad 2: Ako funguje funkcia bsearch () pre viac ako jeden zodpovedajúci prvok?
#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; )
Po spustení programu bude možný výstup:
14 nájdené v polohe 7
