AddressSanitizer栈溢出问题求助：二分查找代码报错排查

核心原因：无限递归耗尽栈空间 #

你的代码存在两处关键错误，直接引发无限递归，最终导致栈溢出：

1. 递归区间未正确收缩

   • 当arr[mid] > x时，目标值在左半区间，应递归调用binarySearch(arr, l, mid-1, x)，但你写的是binarySearch(arr, mid, r, x)——右边界未左移，每次递归仍包含mid，区间无法缩小。
   • 当arr[mid] < x时，目标值在右半区间，应递归调用binarySearch(arr, mid+1, r, x)，但你写的是binarySearch(arr, l, mid, x)——左边界未右移，区间同样无法收缩。
     这种错误会让递归永远无法终止，不断创建新栈帧，最终耗尽栈空间。

2. 缺失递归终止的边界判断
   当l > r时，说明整个区间已搜索完毕、目标值不存在，此时应直接返回-1。你的代码未处理该情况，反而在最后返回0，既逻辑错误，又让无效区间的递归持续进行。

3. 递归调用未返回结果
   递归调用语句后未添加return，比如binarySearch(arr, mid, r, x)仅执行函数，但未将递归结果返回给上层调用，这会导致找到目标值时无法正确返回索引（虽非栈溢出直接原因，但属于逻辑错误）。

修正后的代码示例 #

int binarySearch(int* arr,int l,int r,int x){
    // 边界条件：区间无效，返回-1
    if(l > r){
        return -1;
    }
    int mid = (l + r) / 2;
    if(arr[mid] == x){
        return mid;
    }
    else if(arr[mid] > x){
        // 搜索左半区间，右边界设为mid-1
        return binarySearch(arr, l, mid-1, x);
    }
    else{
        // 搜索右半区间，左边界设为mid+1
        return binarySearch(arr, mid+1, r, x);
    }
}
int search(int* nums, int numsSize, int target){
    return binarySearch(nums, 0, numsSize-1, target);
}

内容的提问来源于stack exchange，提问作者Dark Fire Master