Funkcja bsearch () w C ++ wykonuje binarne wyszukiwanie elementu w tablicy elementów i zwraca wskaźnik do elementu, jeśli zostanie znaleziony.
Funkcja bsearch () wymaga, aby wszystkie elementy były mniejsze niż element do przeszukania znajdujący się po lewej stronie tablicy.
Podobnie wszystkie elementy większe niż element do przeszukania muszą znajdować się po prawej stronie tablicy. To wymaganie jest spełnione, jeśli tablica jest posortowana w porządku rosnącym.
prototyp bsearch ()
void * bsearch (const void * key, const void * base, size_t num, size_t size, int (* compare) (const void *, const void *));
Funkcja jest zdefiniowana w pliku nagłówkowym.
Funkcja bsearch () wyszukuje klucz w bazie tablicy. Wszystkie elementy mniejsze niż klucz muszą pojawić się przed nim w bazie tablicy. Podobnie wszystkie elementy większe niż klucz muszą pojawić się po nim w base.
Aby przeprowadzić wyszukiwanie, funkcja bsearch () wykonuje serię wywołań funkcji wskazanej przez porównanie z kluczem jako pierwszym argumentem i elementem z tablicy jako drugim argumentem.
bsearch () Parametry
- klucz: wskaźnik do elementu do wyszukania
- base: wskaźnik do pierwszego elementu tablicy
- num: numer elementu w tablicy
- size: rozmiar w bajtach każdego elementu w tablicy
- porównaj: wskaźnik do funkcji, która porównuje dwa elementy. Wraca
- ujemna liczba całkowita, jeśli pierwszy argument jest mniejszy niż drugi
- dodatnią liczbą całkowitą, jeśli pierwszy argument jest większy niż drugi
- zero, jeśli oba argumenty są równe
klucz jest przekazywany jako pierwszy argument, a element z tablicy jest przekazywany jako drugi argument. Prototyp funkcji porównania wygląda następująco:
int compare (const void * a, const void * b);
bsearch () Zwracana wartość
Funkcja bsearch () zwraca:
- Wskaźnik do znalezionego elementu. Jeśli zostanie znalezionych więcej niż jeden pasujący element, nie jest określone, który adres elementu funkcja zwróci jako wynik.
- Wskaźnik pusty, jeśli element nie zostanie znaleziony.
Przykład 1: Jak działa funkcja 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; )
Po uruchomieniu programu wynik będzie następujący:
10 znaleziono na pozycji 2 15 nie znaleziono
Przykład 2: Jak funkcja bsearch () działa dla więcej niż jednego pasującego elementu?
#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; )
Po uruchomieniu programu możliwe wyjście to:
14 znaleziono na pozycji 7
