用C++编写实现二分搜索的递归与非递归程序

下面是用C++编写的二分搜索的递归和非递归版本程序示例：

#include <iostream>
using namespace std;

// 递归版本
int binarySearchRecursive(int arr[], int left, int right, int target) {
    if (left <= right) {
        int mid = left + (right - left) / 2;

        // 如果目标元素等于中间元素，则返回中间元素的索引
        if (arr[mid] == target)
            return mid;

        // 如果目标元素小于中间元素，则在左半部分递归执行搜索
        if (arr[mid] > target)
            return binarySearchRecursive(arr, left, mid - 1, target);

        // 如果目标元素大于中间元素，则在右半部分递归执行搜索
        return binarySearchRecursive(arr, mid + 1, right, target);
    }

    // 如果左指针大于右指针，则返回不存在的标记
    return -1;
}

// 非递归版本
int binarySearchIterative(int arr[], int left, int right, int target) {
    while (left <= right) {
        int mid = left + (right - left) / 2;

        // 如果目标元素等于中间位置的值，则返回中间位置
        if (arr[mid] == target)
            return mid;

        // 如果目标元素小于中间位置的值，则将右指针更新为中间位置-1
        if (arr[mid] > target)
            right = mid - 1;

        // 如果目标元素大于中间位置的值，则将左指针更新为中间位置+1
        else
            left = mid + 1;
    }

    // 如果左指针大于右指针，则返回不存在的标记
    return -1;
}

int main() {
    int n;
    cout << "输入数组长度：";
    cin >> n;

    int arr[n];
    cout << "输入有序数组元素：";
    for (int i = 0; i < n; i++)
        cin >> arr[i];

    int target;
    cout << "输入待查找的数值：";
    cin >> target;

    int recursiveResult = binarySearchRecursive(arr, 0, n - 1, target);
    int iterativeResult = binarySearchIterative(arr, 0, n - 1, target);

    cout << "递归版本结果：" << recursiveResult << endl;
    cout << "非递归版本结果：" << iterativeResult << endl;

    return 0;
}

这个程序首先要求用户输入数组长度和数组元素，然后输入待查找的数值。接下来，使用递归版本的二分搜索算法和非递归版本的二分搜索算法在给定的数组中查找目标数值，并输出结果。

请注意，在编译和运行此程序之前，确保您的C++编译器已正确安装并配置。

希望这个示例能帮助到您！