C++实现Binary Search未匹配元素时返回垃圾值而非0的问题

问题原因 #

• 核心错误：递归分支调用BinarySearch时未加return关键字。当目标值不等于中间位置元素、需要递归查找左右子区间时，代码仅执行了递归调用，但没有将递归得到的结果向上层返回，函数执行完递归语句后直接走到分支结尾，无匹配的return语句，此时返回值属于未定义行为，就会输出随机垃圾值。
• 逻辑漏洞：约定返回0标识元素未找到，但vector合法下标从0开始，若目标元素恰好存储在下标0的位置，会被误判为不存在。
• 性能问题：vector参数采用值传递，每次递归都会完整拷贝整个容器，数据量较大时性能损耗明显。
• 语法不规范：main函数未声明返回类型，不符合标准C++语法要求。

修复方法 #

• 两处递归调用BinarySearch前补充return，保证子问题的查找结果能逐层返回到最上层调用
• 将未找到元素的返回值改为-1（不属于合法下标范围），同步调整main函数中的判断逻辑
• vector形参改为const引用传递，避免不必要的容器拷贝
• 为main函数补充int返回类型，函数末尾添加return 0

修复后完整代码 #

#include<iostream>
#include<vector>
using namespace std;

int BinarySearch(const vector<int>& v, int x, int y, int t) {
    if (x > y) {
        return -1; // 返回-1标识元素未找到，避免和合法下标0冲突
    }
    int m = x + (y - x) / 2;
    if (v[m] == t) {
        return m;
    } else if (v[m] > t) {
        return BinarySearch(v, x, m - 1, t); // 补充return返回左区间查找结果
    } else {
        return BinarySearch(v, m + 1, y, t); // 补充return返回右区间查找结果
    }
}

int main() {
    int n, m = 0, no;
    vector<int> v;
    cout << "Enter the No of Elements u wanna store in the Array : ";
    cin >> n;
    while (n--) {
        cout << "Enter Element " << ++m << " : ";
        int t;
        cin >> t;
        v.push_back(t);
    }
    cout << "Enter the no u wanna search for : ";
    cin >> no;
    int Start = 0, End = v.size() - 1;
    int B = BinarySearch(v, Start, End, no);
    if (B == -1) {
        cout << "Element not Found\n";
    } else {
        cout << "The Element is at position: " << B + 1;
    }
    return 0;
}

补充说明：二分查找仅对升序排列的有序区间有效，如果输入的vector元素未排序，查找结果会出错。

内容的提问来源于stack exchange，提问作者Abhishek