Funkce bsearch () v C ++ provádí binární vyhledávání prvku v poli prvků a vrací ukazatel na prvek, pokud je nalezen.
Funkce bsearch () vyžaduje, aby byly v poli nalevo od něj prohledávány všechny prvky menší než prvek.
Stejně tak všechny prvky větší než hledaný prvek musí být napravo od něj v poli. Tento požadavek je splněn, pokud je pole seřazeno vzestupně.
prototyp bsearch ()
void * bsearch (const void * klíč, const void * base, size_t počet, size_t velikost, int (* porovnat) (const void *, const void *));
Funkce je definována v hlavičkovém souboru.
Funkce bsearch () hledá klíč v základně pole. V základu pole se před ním musí objevit všechny prvky menší než klíč. Stejně tak se po něm v základně musí objevit všechny prvky větší než klíč.
Chcete-li provést vyhledávání, provede funkce bsearch () řadu volání funkce, na kterou ukazuje srovnání s klíčem jako prvním argumentem a prvkem z pole jako druhým argumentem.
bsearch () parametry
- klíč: Ukazatel na prvek, který se má vyhledat
- base: Ukazatel na první prvek pole
- num: Počet prvků v poli
- size: Velikost v bajtech každého prvku v poli
- porovnat: Ukazatel na funkci, která porovnává dva prvky. Vrací se
- záporné celé číslo, pokud je první argument menší než druhý
- kladné celé číslo, pokud je první argument větší než druhý
- nula, pokud jsou oba argumenty stejné
klíč je předán jako první argument a prvek z pole je předán jako druhý argument. Prototyp srovnávací funkce vypadá takto:
int porovnat (const void * a, const void * b);
bsearch () Vrátí hodnotu
Funkce bsearch () vrací:
- Ukazatel na nalezený prvek. Pokud je nalezeno více než jeden odpovídající prvek, pak je nespecifikováno, která adresa prvku bude jako výsledek funkce vrácena.
- Nulový ukazatel, pokud prvek nebyl nalezen.
Příklad 1: Jak funguje funkce 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; )
Když spustíte program, výstup bude:
10 nalezeno na pozici 2 15 nenalezeno
Příklad 2: Jak funguje funkce bsearch () pro více než jeden odpovídající prvek?
#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; )
Při spuštění programu bude možný výstup:
14 nalezeno v poloze 7
