C ++: n bsearch () -funktio suorittaa elementtiryhmän elementin binäärisen haun ja palauttaa osoittimen elementille, jos se löytyy.
Bsearch () -funktio edellyttää, että kaikki elementtiä pienemmät elementit etsitään matriisista sen vasemmalta puolelta.
Samoin kaikkien etsittävän elementin suurempien elementtien on oltava taulukon oikealla puolella. Tämä vaatimus täyttyy, jos taulukko on lajiteltu nousevassa järjestyksessä.
bsearch () -prototyyppi
void * bsearch (const void * avain, const void * pohja, size_t numero, size_t koko, int (* vertaa) (const void *, const void *));
Toiminto määritetään otsikkotiedostossa.
Bsearch () -toiminto etsii avainta taulukon pohjasta. Kaikkien alle avainta sisältävien elementtien on oltava ennen sitä matriisipohjassa. Samoin kaikkien avainta suurempien elementtien on oltava sen perässä.
Haun suorittamiseksi bsearch () -funktio tekee sarjan kutsuja funktiolle, jota vertaillaan avainten kanssa ensimmäiseksi argumentiksi ja taulukon elementiksi toisena argumenttina.
bsearch () -parametrit
- avain: Osoittimen etsittävä elementti
- pohja: Osoitin taulukon ensimmäiseen elementtiin
- num: matriisin elementin numero
- size: Matriisin kunkin elementin koko tavuina
- vertaa: Osoitin funktioon, joka vertaa kahta elementtiä. Se palaa
- negatiivinen kokonaisluku, jos ensimmäinen argumentti on pienempi kuin toinen
- positiivinen kokonaisluku, jos ensimmäinen argumentti on suurempi kuin toinen
- nolla, jos molemmat argumentit ovat samat
avain välitetään ensimmäisenä argumenttina ja taulukon elementti välitetään toisena argumenttina. Vertailutoiminnon prototyyppi näyttää tältä:
int vertaa (const void * a, const void * b);
bsearch () Palautusarvo
Bsearch () -funktio palauttaa:
- Osoitin löydettyyn elementtiin. Jos löytyy useampi kuin yksi yhteensopiva elementti, ei ole määritelty, minkä elementin osoitteen funktio palauttaa tuloksena.
- Nollaosoitin, jos elementtiä ei löydy.
Esimerkki 1: Kuinka bsearch () -toiminto toimii?
#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; )
Kun suoritat ohjelmaa, tulos on:
10 löydetty sijainnista 2 15 ei löydy
Esimerkki 2: Kuinka bsearch () -toiminto toimii useammalle kuin yhdelle vastaavalle elementille?
#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; )
Kun suoritat ohjelmaa, mahdollinen tulos on:
14 löydetty asemasta 7
