使用递归函数实现二分查找用c++

在C++中，递归函数可以用于实现二分查找算法（Binary Search），这是一种在有序数组中查找特定元素的搜索策略。二分查找的基本思想是从数组的中间元素开始比较，如果目标值等于中间元素，则返回该位置；如果目标值小于中间元素，则在左半部分继续查找；如果目标值大于中间元素，则在右半部分查找。这个过程会一直持续到找到目标值或搜索范围为空。

下面是一个简单的C++递归实现二分查找的例子：

#include <iostream>
using namespace std;

int binarySearch(int arr[], int low, int high, int target) {
    // Base case: 如果low大于high，说明找不到目标，返回-1
    if (low > high)
        return - low) / 2;

    // 检查中间元素是否为目标
    if (arr[mid] == target)
        return mid;

    // 如果目标比中间大，就在右半部分找
    else if (arr[mid] > target)
        return binarySearch(arr, low, mid - 1, target);

    // 否则，在左半部分找
    else
        return binarySearch(arr, mid + 1, high, target);
}

int main() {
    int arr[] = {1, 3, 5, 7, 9};
    int size = sizeof(arr) / sizeof(arr[0]);
    int target = 5;
    int result = binarySearch(arr, 0, size - 1, target);
    if (result != -1)
        cout << "Element found at index " << result << endl;
    else
        cout << "Element not found" << endl;
    return 0;
}