C++代码使用减治思想实现折半查找

在C++中，折半查找（Binary Search），也称为二分搜索，是一种在有序数组中查找特定元素的算法。它通过反复将数据集分成两半来进行查找，直到找到目标值或确定其不存在于数组中。以下是使用减治法（Divide and Conquer）思想实现折半查找的一个简单C++版本：

#include <iostream>

// 定义折半查找的函数
int binarySearch(int arr[], int left, int right, int target) {
    if (left > right) // 如果左边界大于右边界，说明数组为空或目标不在数组中
        return -1;

    int mid = left + (right - left) / 2; // 计算中间位置

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

    // 如果目标小于中间元素，我们在左半边继续查找
    else if (arr[mid] > target)
        return binarySearch(arr, left, mid - 1, target);

    // 否则，我们在右半边查找
    else
        return binarySearch(arr, mid + 1, right, target);
}

int main() {
    int arr[] = {1, 3, 5, 7, 9}; // 示例数组，已排序
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 5;
    int result = binarySearch(arr, 0, n - 1, target);

    if (result != -1)
        std::cout << "Element found at index " << result << std::endl;
    else
        std::cout << "Element not found in the array" << std::endl;

    return 0;
}

在这个代码中，函数`binarySearch`递归地将查找范围缩小，直到找到目标或确认目标不存在。如果找到了，返回索引；如果没有找到，则返回-1。