Tìm kiếm nhị phân (Binary Search) trong C++

Tìm kiếm nhị phân (Binary Search) tìm phần tử trong mảng đã sắp xếp bằng cách chia đôi liên tục mảng và tìm ở nửa phù hợp.

Bắt đầu từ toàn mảng. Tính mid. Nếu giá trị tìm > a[mid] → tìm nửa trên. Ngược lại tìm nửa dưới. Lặp lại cho đến khi tìm thấy hoặc mảng rỗng.

Ví dụ

#include <iostream>
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;
}

Kết quả

Enter the number to search: 20
20 is present at index 5 in the array

Hàm binarySearch() đệ quy

Tham số: mảng, giới hạn dưới p, giới hạn trên r, số cần tìm num.

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;
}

Hàm main()

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;
}