Hàm bsearch () trong C ++ thực hiện tìm kiếm nhị phân một phần tử trong một mảng phần tử và trả về một con trỏ đến phần tử nếu được tìm thấy.
Hàm bsearch () yêu cầu tất cả các phần tử nhỏ hơn phần tử được tìm kiếm ở bên trái của nó trong mảng.
Tương tự như vậy, tất cả các phần tử lớn hơn phần tử được tìm kiếm phải ở bên phải của nó trong mảng. Yêu cầu này được đáp ứng nếu mảng được sắp xếp theo thứ tự tăng dần.
bsearch () nguyên mẫu
void * bsearch (const void * key, const void * base, size_t num, size_t size, int (* so sánh) (const void *, const void *));
Hàm được định nghĩa trong tệp tiêu đề.
Hàm bsearch () tìm kiếm khóa trong cơ sở mảng. Tất cả các phần tử nhỏ hơn khóa phải xuất hiện trước nó trong cơ sở mảng. Tương tự như vậy, tất cả các phần tử lớn hơn key phải xuất hiện sau nó trong cơ sở.
Để thực hiện tìm kiếm, hàm bsearch () thực hiện một loạt lệnh gọi hàm được trỏ tới bằng cách so sánh với key là đối số đầu tiên và một phần tử từ mảng làm đối số thứ hai.
bsearch () Tham số
- key: Con trỏ đến phần tử cần tìm kiếm
- base: Con trỏ đến phần tử đầu tiên của mảng
- num: Số phần tử trong mảng
- size: Kích thước tính bằng byte của mỗi phần tử trong mảng
- so sánh: Một con trỏ đến một hàm so sánh hai phần tử. Nó trở lại
- một số nguyên âm nếu đối số đầu tiên nhỏ hơn đối số thứ hai
- một số nguyên dương nếu đối số đầu tiên lớn hơn đối số thứ hai
- không nếu cả hai đối số bằng nhau
key được chuyển làm đối số đầu tiên và một phần tử từ mảng được chuyển làm đối số thứ hai. Nguyên mẫu của hàm so sánh trông giống như sau:
int so sánh (const void * a, const void * b);
bsearch () Giá trị trả về
Hàm bsearch () trả về:
- Trỏ đến phần tử tìm được. Nếu tìm thấy nhiều phần tử phù hợp, thì kết quả là không xác định được địa chỉ của phần tử nào mà hàm sẽ trả về.
- Con trỏ rỗng nếu phần tử không được tìm thấy.
Ví dụ 1: Hàm bsearch () hoạt động như thế nào?
#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; )
Khi bạn chạy chương trình, đầu ra sẽ là:
10 được tìm thấy ở vị trí 2 15 không tìm thấy
Ví dụ 2: Hàm bsearch () hoạt động như thế nào đối với nhiều hơn một phần tử phù hợp?
#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; )
Khi bạn chạy chương trình, đầu ra có thể sẽ là:
14 được tìm thấy ở vị trí 7
