C++编写减治算法,求解折半查找问题

折半查找，也称二分查找，是一种在有序数组中快速查找特定元素的搜索算法。在C++中实现这种算法并不复杂，以下是基本步骤：

1. 定义函数模板，假设名字为`binarySearch`，接受一个已排序的整数数组`arr`，以及两个索引下标`low`和`high`作为参数：

template <typename T>
T binarySearch(const T arr[], int low, int high, T target) {

2. 检查基本情况：如果`low`大于`high`，说明目标不在数组内，返回`-1`表示未找到。

if (low > high)
    return -1;

3. 计算中间索引`mid`，并比较中间元素和目标值：

int mid = low + (high - low) / 2;
if (arr[mid] == target)
    return mid;

4. 如果目标小于中间元素，就在左半部分继续查找；反之，在右半部分查找：

if (target < arr[mid])
    return binarySearch(arr, low, mid - 1, target);
else
    return binarySearch(arr, mid + 1, high, target);

5. 最终函数会递归地缩小搜索范围，直到找到目标或确定目标不存在。

完整代码示例：

#include <iostream>

// 为了方便测试，我们提供一个包含元素的辅助函数
std::vector<int> generateArray(int size, int start, int end) {
    std::vector<int> array(size);
    for (int i = 0; i < size; ++i)
        array[i] = start + i * (end - start + 1) / size;
    return array;
}

template <typename T>
T binarySearch(const T arr[], int low, int high, T target) {
    // ... (以上代码)
}

int main() {
    std::vector<int> sortedArray = generateArray(10, 1, 100);
    int target = 50;
    int result = binarySearch(sortedArray.data(), 0, sortedArray.size() - 1, target);
    if (result != -1)
        std::cout << "Element found at index: " << result << std::endl;
    else
        std++.cout << "Element not found." << std::endl;

    return 0;
}