Funkcija bsearch () v jeziku C ++ izvede binarno iskanje elementa v nizu elementov in vrne kazalec na element, če ga najde.
Funkcija bsearch () zahteva, da se v levi od polja v polju iščejo vsi elementi, manjši od elementa.
Prav tako morajo biti vsi elementi, večji od iskanega elementa, desno od njega v polju. Ta zahteva je izpolnjena, če je polje razvrščeno po naraščajočem vrstnem redu.
prototip bsearch ()
void * bsearch (const void * key, const void * base, size_t num, size_t size, int (* primerjaj) (const void *, const void *));
Funkcija je definirana v glavi datoteke.
Funkcija bsearch () išče ključ v bazi matrike. Vsi elementi, manjši od ključa, se morajo pred njim prikazati v osnovi matrike. Prav tako se morajo vsi elementi, večji od ključa, pojaviti za njim v bazi.
Da bi izvedla iskanje, funkcija bsearch () izvede niz klicev na funkcijo, na katero opozori primerjava s ključem kot prvim argumentom in elementom iz polja kot drugim argumentom.
parametri bsearch ()
- tipka: Kazalec na element za iskanje
- osnova: Kazalec na prvi element polja
- num: Število elementov v matriki
- velikost: Velikost v bajtih vsakega elementa v matriki
- compare: Kazalec na funkcijo, ki primerja dva elementa. Vrne se
- negativno celo število, če je prvi argument manjši od drugega
- pozitivno celo število, če je prvi argument večji od drugega
- nič, če sta oba argumenta enaka
Ključ se preda kot prvi argument, element iz polja pa kot drugi argument. Prototip funkcije primerjave je videti tako:
int primerjaj (const void * a, const void * b);
bsearch () Vrnjena vrednost
Funkcija bsearch () vrne:
- Kazalec na najdeni element. Če je najdenih več kot enakovrednih elementov, potem ni določeno naslova katerega elementa bo funkcija vrnila kot rezultat.
- Nič kazalec, če elementa ni mogoče najti.
Primer 1: Kako deluje 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; )
Ko zaženete program, bo rezultat:
10 najdeno na položaju 2 15 ni najdeno
Primer 2: Kako funkcija bsearch () deluje za več kot en ujemajoč se 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; )
Ko zaženete program, bo možen izhod:
14 najdeno na položaju 7
