【递归】二分查找（C++）

Question

【递归】二分查找
描述

用递归算法实现二分查找，即：有n个已经从小到大排序好的数据（不重复），从键盘输入一个数X，用对半查找方法，判断它是否在这n个数中。

输入

第一行，正整数n，N<=10^5；

第二行，n个整数（int范围内，不重复），中间用空格分隔；

第三行，整数X。

输出

如果找到X，输出其位置；否则输出-1。

输入样例 1

10
10 20 30 40 50 60 70 80 90 100
90
输出样例 1

9

Answer 1

以下回复参考：皆我百晓生、券券喵儿等免费微信小程序作答:

这是一个二分查找的递归实现的问题。在二分查找中，我们假设有一个排序好的数组，并且我们正在寻找一个特定的值。如果数组为空或者我们找到了我们正在查找的值，那么递归就会停止。否则，我们将数组分成两半，并在其中一半上递归调用二分查找。以下是一个可能的C++实现：

#include <iostream>
using namespace std;

int binarySearchRecursive(int arr[], int n, int target, int low, int high) {
    if (low > high) {  // 如果low大于high，说明没有找到目标值
        return -1;
    }
    int mid = low + (high - low) / 2;  // 避免溢出问题，正确计算中间位置
    if (arr[mid] == target) {  // 如果找到目标值，返回其位置
        return mid;
    } else if (arr[mid] > target) {  // 如果目标值小于中间值，搜索左半部分数组
        return binarySearchRecursive(arr, n, target, low, mid - 1);
    } else {  // 如果目标值大于中间值，搜索右半部分数组
        return binarySearchRecursive(arr, n, target, mid + 1, high);
    }
}

int main() {
    int n;
    cin >> n;  // 输入正整数n
    int arr[n];  // 输入n个整数并存储在数组中
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    int target;  // 输入要查找的整数X
    cin >> target;
    int result = binarySearchRecursive(arr, n, target, 0, n - 1);  // 开始递归二分查找
    cout << result << endl;  // 输出结果，如果找到则输出位置，否则输出-1
    return 0;
}

这段代码首先定义了一个递归函数 binarySearchRecursive 来执行二分查找。然后在 main 函数中，我们输入正整数 n 来定义数组的大小，接着输入 n 个整数作为数组元素，再输入要查找的整数 target。最后我们调用 binarySearchRecursive 函数开始查找并输出结果。