1. 编写递归函数，实现二分查找问题。c++

二分查找算法通常用于已排序的数组中，它通过不断将搜索范围减半来找到目标元素。在C++中编写递归版本的二分查找函数，可以按照以下步骤：

#include <iostream>

// 定义递归函数模板，输入是要查找的数组、范围的起始索引、结束索引以及目标值
template<typename T, typename Compare = std::less<T>>
T binarySearch(T arr[], int low, int high, const T& target) {
    // 基线条件：如果低索引大于高索引，说明未找到目标，返回 -1 或者根据需求指定的默认值
    if (low > high)
        return high == -1 ? high : -1;

    // 计算中间索引
    int mid = low + (high - low) / 2;

    // 检查中间元素是否等于目标
    if (Compare()(arr[mid], target)) { // 如果小于目标，向右半部分递归
        return binarySearch(arr, mid + 1, high, target);
    } else if (Compare()(target, arr[mid])) { // 否则，向左半部分递归
        return binarySearch(arr, low, mid - 1, target);
    } else {
        // 找到目标，返回中间索引
        return mid;
    }
}

int main() {
    // 测试示例
    int sortedArray[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    int target = 5;
    int index = binarySearch(sortedArray, 0, sizeof(sortedArray) / sizeof(sortedArray[0]) - 1, target);
    if (index != -1)
        std::cout << "Element found at index " << index << std::endl;
    else
        std::cout << "Element not found" << std::endl;
    return 0;
}