Tìm kiếm nhị phân là một phương pháp để tìm phần tử bắt buộc trong một mảng được sắp xếp bằng cách lặp lại một nửa mảng và tìm kiếm một nửa.
Phương pháp này được thực hiện bằng cách bắt đầu với toàn bộ mảng. Sau đó, nó được giảm một nửa. Nếu giá trị dữ liệu bắt buộc lớn hơn phần tử ở giữa mảng, thì nửa trên của mảng được coi là. Nếu không, nửa dưới được coi là. Điều này được thực hiện liên tục cho đến khi nhận được giá trị dữ liệu cần thiết hoặc mảng còn lại trống.
Dưới đây là một chương trình thể hiện tìm kiếm nhị phân trong C ++.
Ví dụ
#include
using namespace std;
int binarySearch(int arr[], int p, int r, int num) {
if (p <= r) {
int mid = (p + r)/2;
if (arr[mid] == num)
return mid ;
if (arr[mid] > num)
return binarySearch(arr, p, mid-1, num);
if (arr[mid] < num)
return binarySearch(arr, mid+1, r, num);
}
return -1;
}
int main(void) {
int arr[] = {1, 3, 7, 15, 18, 20, 25, 33, 36, 40};
int n = sizeof(arr)/ sizeof(arr[0]);
int num;
cout << "Enter the number to search: \n";
cin >> num;
int index = binarySearch (arr, 0, n-1, num);
if(index == -1){
cout<< num <<" is not present in the array";
}else{
cout<< num <<" is present at index "<< index <<" in the array";
}
return 0;
} Đầu ra
Enter the numberto search 20 20 is present at index 5 in the array
Trong chương trình trên, binarySearch () là một hàm đệ quy được sử dụng để tìm phần tử cần thiết trong mảng bằng cách sử dụng tìm kiếm nhị phân. Hàm nhận mảng, giới hạn dưới và giới hạn trên của nó cũng như số được tìm thấy làm tham số. Điều này được hiển thị bên dưới.
int binarySearch(int arr[], int p, int r, int num)
Sau đó, điểm giữa của mảng được tính. Nếu giá trị tại điểm giữa bằng num, thì nó được trả về. Nếu giá trị lớn hơn num, thì mảng tự gọi đệ quy với giới hạn dưới p và giới hạn trên giữa 1. Nếu giá trị nhỏ hơn num, thì mảng tự gọi đệ quy với giới hạn dưới giữa + 1 và giới hạn trên r. Đoạn mã sau có thể thấy điều này.
int binarySearch(int arr[], int p, int r, int num) {
if (p <= r) {
int mid = (p + r)/2;
if (arr[mid] == num)
return mid ;
if (arr[mid] > num)
return binarySearch(arr, p, mid-1, num);
if (arr[mid] < num)
return binarySearch(arr, mid+1, r, num);
}
return -1;
} Trong hàm main (), mảng arr [] được định nghĩa. Kích thước của mảng được tính toán và số lượng cần tìm được chỉ định. Sau đó, binarySearch () được gọi để tìm chỉ số của số. Nếu giá trị được trả về bởi binarySearch () là -1, thì số đó không có trong mảng. Nếu không, giá trị chỉ mục được trả về. Điều này được đưa ra bên dưới.
int main(void) {
int arr[] = {1, 3, 7, 15, 18, 20, 25, 33, 36, 40};
int n = sizeof(arr)/ sizeof(arr[0]);
int num = 33;
int index = binarySearch (arr, 0, n-1, num);
if(index == -1)
cout<< num <<" is not present in the array";
else
cout<< num <<" is present at index "<< index <<" in the array";
return 0;
}