递归实现Binary Search查找数组元素时触发Segmentation Fault问题排查

一、触发段错误的直接原因：vector越界访问 #

你的main函数中，创建了空的vector<int> arr后直接通过arr[j]赋值，此时vector没有分配任何存储空间，访问下标会直接触发段错误。

二、递归二分查找的核心逻辑错误 #

除了段错误，你的递归查找逻辑完全不符合二分查找的设计：

• 多余的for循环：递归二分查找不需要循环，每次递归就是一次范围缩小的判断，循环会导致逻辑混乱，甚至引发无限递归。
• 递归参数未传递更新后的范围：每次递归都重新初始化low=0和high=arr.size()-1，没有把上一步缩小后的low/high传给下一层递归，导致每次递归都在整个数组中查找，无法定位目标，最终可能栈溢出。
• 递归调用未返回结果：递归调用recursivebinarysearch后没有写return，导致函数在部分路径下没有返回值，触发未定义行为。
• ans参数逻辑错误：ans参数没有实际作用，找到目标时错误地将mid赋值给ans再返回ans，完全不符合查找目标下标或存在性的需求。

三、修复后的完整代码 #

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

// 修复后的递归二分查找：传递low和high作为参数，明确终止条件
int recursivebinarysearch(vector<int>& arr, int target, int low, int high){
    // 终止条件：范围无效，返回-1表示未找到
    if(low > high){
        return -1;
    }
    int mid = low + (high - low)/2; // 避免high+low溢出
    if(target > arr[mid]){
        // 目标在右半区，递归查找右半部分
        return recursivebinarysearch(arr, target, mid + 1, high);
    }
    else if(target < arr[mid]){
        // 目标在左半区，递归查找左半部分
        return recursivebinarysearch(arr, target, low, mid - 1);
    }
    else{
        // 找到目标，返回下标
        return mid;
    }
}

int main(){
    int n, target;
    cin >> n ;
    
    vector<int> arr;
    // 用push_back添加元素，避免越界
    for(int j = 0 ; j < n ; j++){
        int num;
        cin >> num;
        arr.push_back(num);
    }
    cin >> target ;
    sort(arr.begin() , arr.end());
    // 初始范围是整个数组：low=0，high=arr.size()-1
    int ans = recursivebinarysearch(arr, target, 0, arr.size()-1);

    cout << ans << endl;

    return 0;
}

四、避免此类问题的注意事项 #

• 容器操作先确保空间有效：使用vector时，要么提前用resize(n)分配空间，要么用push_back添加元素，禁止直接访问空vector的下标。
• 递归算法明确参数与终止条件：递归函数的参数必须包含每次递归需要更新的状态（比如二分查找的low和high），同时必须有清晰的终止条件，避免无限递归。
• 确保函数所有路径都有返回值：非void函数必须保证任何执行路径都能返回对应类型的值，否则会触发未定义行为。
• 二分查找避免溢出：计算mid时用low + (high - low)/2代替(low+high)/2，防止两个大整数相加溢出。

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