Funktionen bsearch () i C ++ utför en binär sökning av ett element i en rad element och returnerar en pekare till elementet om det hittas.
Funktionen bsearch () kräver att alla element som är mindre än elementet ska sökas till vänster om det i matrisen.
På samma sätt måste alla element som är större än det element som ska sökas vara till höger om det i matrisen. Detta krav uppfylls om matrisen sorteras i stigande ordning.
bsearch () prototyp
void * bsearch (const void * key, const void * base, size_t num, size_t size, int (* jämför) (const void *, const void *));
Funktionen definieras i rubrikfilen.
Funktionen bsearch () söker efter nyckel i arraybasen. Alla element mindre än nyckeln måste visas före den i arraybasen. På samma sätt måste alla element som är större än nyckeln visas efter det i basen.
För att utföra sökningen gör funktionen bsearch () en serie samtal till funktionen som pekas genom att jämföra med tangent som det första argumentet och ett element från matrisen som det andra argumentet.
bsearch () Parametrar
- tangent: pekare till det element du vill söka
- bas: pekare till det första elementet i matrisen
- num: Antal element i matrisen
- storlek: Storlek i byte för varje element i matrisen
- jämför: En pekare till en funktion som jämför två element. Den återvänder
- ett negativt heltal om det första argumentet är mindre än det andra
- ett positivt heltal om det första argumentet är större än det andra
- noll om båda argumenten är lika
nyckeln skickas som det första argumentet och ett element från matrisen skickas som det andra argumentet. Prototypen för jämförelsefunktionen ser ut som:
int jämför (const void * a, const void * b);
bsearch () Returvärde
Funktionen bsearch () returnerar:
- Pekare till det hittade elementet. Om fler än ett matchande element hittas är det ospecificerat vilket element adress funktionen kommer att returnera som resultat.
- Nollpekare om elementet inte hittas.
Exempel 1: Hur fungerar bsearch () -funktionen?
#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; )
När du kör programmet blir resultatet:
10 hittade vid position 2 15 hittades inte
Exempel 2: Hur fungerar bsearch () -funktionen för mer än ett matchande 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; )
När du kör programmet blir en möjlig utdata:
14 hittade vid position 7
