Funcția bsearch () din C ++ efectuează o căutare binară a unui element dintr-o matrice de elemente și returnează un indicator către element dacă este găsit.
Funcția bsearch () necesită căutarea tuturor elementelor mai mici decât elementul în stânga acestuia în matrice.
În mod similar, toate elementele mai mari decât elementul de căutat trebuie să fie în dreapta acestuia în matrice. Această cerință este îndeplinită dacă matricea este sortată în ordine crescătoare.
bsearch () prototip
void * bsearch (const void * key, const void * base, size_t num, size_t size, int (* compare) (const void *, const void *));
Funcția este definită în fișierul antet.
Funcția bsearch () caută cheia în baza matricei. Toate elementele mai mici decât cheia trebuie să apară în fața acesteia în baza matricei. La fel, toate elementele mai mari decât cheia trebuie să apară după ea în bază.
Pentru a efectua căutarea, funcția bsearch () efectuează o serie de apeluri către funcția indicată prin compararea cu cheia ca prim argument și un element din matrice ca al doilea argument.
bsearch () Parametri
- tasta: Pointer către elementul de căutat
- bază: Pointer către primul element al matricei
- num: Numărul de element din matrice
- size: Dimensiune în octeți a fiecărui element din matrice
- compare: Un indicator către o funcție care compară două elemente. Se întoarce
- un întreg negativ dacă primul argument este mai mic decât al doilea
- un număr întreg pozitiv dacă primul argument este mai mare decât al doilea
- zero dacă ambele argumente sunt egale
cheia este trecută ca primul argument și un element din matrice este trecut ca al doilea argument. Prototipul funcției de comparație arată ca:
int compare (const void * a, const void * b);
bsearch () Valoare returnată
Funcția bsearch () returnează:
- Pointer către elementul găsit. Dacă se găsesc mai multe elemente potrivite, atunci nu este specificat adresa elementului pe care funcția o va returna ca rezultat.
- Pointer nul dacă elementul nu este găsit.
Exemplul 1: Cum funcționează funcția 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; )
Când rulați programul, ieșirea va fi:
10 găsite la poziția 2 15 nu au fost găsite
Exemplul 2: Cum funcționează funcția bsearch () pentru mai multe elemente potrivite?
#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; )
Când rulați programul, o posibilă ieșire va fi:
14 găsite la poziția 7
