C语言二分查找部分元素查找失败的原因排查

问题原因 #

你代码的核心问题出在二分查找的循环判断条件上：

• 当前你使用while(l < r)作为循环终止条件，当左指针l和右指针r重合时，会直接跳出循环，不会对该重合位置的元素做是否匹配目标值的判断，这就导致所有刚好落在最终重合位置的元素都会被误判为不存在，你测试失败的1、10、21、40都属于这类情况。

举个查找元素1的执行示例：

1. 初始l=0，r=8，mid=(0+8)/2=4，arr[4]=17 > 1，所以r更新为3
2. l=0，r=3，mid=(0+3)/2=1，arr[1]=3 >1，所以r更新为0
3. 此时l == r == 0，不满足l < r的循环条件，直接退出返回-1，没有判断arr[0]就是目标值1

修复方案 #

有两种常用修复方式：

方案1：修改循环条件 #

将循环条件改为while(l <= r)，让左右指针重合时也进入循环做判断，修改后的binarysearch函数如下：

int binarysearch(int arr[], int n, int data){
  int l = 0; 
  int r = n-1;

  while(l <= r){
    int mid = (l + r)/2;
    if(data == arr[mid]){
      return mid;
    }
    else if(data > arr[mid]){
      l = mid + 1;
    }
    else {
      r = mid - 1;
    }
  }
  return -1;
}

方案2：循环结束后补充判断 #

如果保留原有while(l < r)的循环条件，只需要在循环退出后增加一步对重合位置的元素判断即可：

int binarysearch(int arr[], int n, int data){
  int l = 0; 
  int r = n-1;

  while(l < r){
    int mid = (l + r)/2;
    if(data == arr[mid]){
      return mid;
    }
    else if(data > arr[mid]){
      l = mid + 1;
    }
    else {
      r = mid - 1;
    }
  }
  // 补充判断重合位置的元素是否匹配
  return arr[l] == data ? l : -1;
}

额外优化提示：现有代码里的mid = (l + r)/2写法在l和r数值较大时可能出现整数溢出问题，可替换为mid = l + (r - l)/2，计算结果一致且能规避溢出风险。

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