两段二分查找代码差异：为何代码1运行异常而代码2正常？

提交大量测试用例时，递归版二分查找（代码1）无法正常运行，迭代版（代码2）却能流畅执行无报错。即便把代码1里的r = mid改成r = mid -1也解决不了问题，两者的核心差异和问题根源如下：

代码1（递归实现） #

class Solution {
  public:
  int helper(int arr[],int n , int k , int l , int r){
      
        // int mid = (l+r)/2;
        int mid = l+(r-l)/2;
        
        if(l>=r ){
            
            return -1;
            
            
        }
        
        if(arr[mid]==k){
            return mid;
            
        }       
        else if(arr[mid]<k){
            l = mid+1;
            
            
        }
        else{
            r = mid;
            
        }
        return helper(arr,n,k,l,r);
  }
  
  
    int binarysearch(int arr[], int n, int k) {
       
        return helper(arr,n,k,0,n-1);
        
        
        
    }
};

代码2（迭代实现） #

class Solution {
  public:
    int binarysearch(int arr[], int n, int k) {
        int low=0;
        int high=n-1;
        int mid=low+(high-low)/2;
        
        while(low<=high){
            if(arr[mid]==k){
                return mid;
        }
        else if(arr[mid]<k){
            low=mid+1;
        }
        else{
            high=mid-1;
        }
        mid=low+(high-low)/2;
    }
    if(k!=arr[mid]){
        return -1;
    }
    else{
        return mid;
    }
    }
};

核心问题拆解 #

1. 代码1的终止条件完全错误
   代码1里if(l>=r) return -1的逻辑，直接跳过了区间最后一个元素的检查——当l==r时，此时区间只剩一个元素，却直接返回-1，完全不判断这个元素是不是目标值k。比如数组只有一个元素且等于k时，会直接返回错误结果；当目标值正好落在最后一次递归的l==r位置时，也会被漏判。

2. 递归边界处理不当，易触发栈溢出
   即便修改r = mid为r = mid-1，终止条件的问题依然存在。另外原逻辑中，当arr[mid]>k时设置r=mid，会导致区间缩小效率低下，甚至在某些测试用例下出现递归层数过多的情况。当数组规模很大时，递归调用会不断占用系统栈空间，超过栈的容量限制后就会触发栈溢出，这就是大量测试用例下代码1无法运行的直接原因。

3. 迭代实现的天然优势
   代码2用循环实现，没有递归调用栈的限制，无论数组多大都不会出现栈溢出问题。同时终止条件low<=high保证了所有元素都会被检查到，low=mid+1和high=mid-1的边界更新能有效缩小区间，不会出现无限循环或漏判的情况。（注：代码2末尾的判断是多余的，循环结束后直接返回-1即可，因为循环条件已覆盖所有可能的元素）

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