K&R《C程序设计语言》二分查找代码运行无输出问题咨询

问题原因 #

你的测试数组没有任何问题，程序卡住是binsearch函数的逻辑错误触发了死循环。

错误点分析 #

二分查找中，当判定x < v[mid]时，说明目标值仅可能出现在mid左侧的区间，此时需要将右边界调整为mid - 1缩小查找范围，但你的代码里错误写为：

if (x < v[mid])
  high = mid + 1;

以你给出的测试用例为例：

• 初始low=0，high=2，计算得mid=1，v[mid]值为4
• 3 < 4，按错误逻辑high被设置为1+1=2
• 下一次循环low和high还是0和2，会重复执行上述逻辑，永远无法跳出while循环，因此程序不会有输出，看起来像编译卡住（实际是运行阶段死循环）

修正方案 #

把上述错误行改为high = mid - 1即可，修正后的完整binsearch函数如下：

/* binsearch: find x in v[0] <= v[1] <= ... <= v[n-1] */
int binsearch(int x, int v[], int n){
  int low, high, mid;
  low = 0;
  high = n - 1;
  while (low <= high) {
    mid = (low+high)/2;
    if (x < v[mid])
      high = mid - 1;
    else if (x > v[mid])
      low = mid + 1;
    else /* found match */
      return mid;
  }
  return -1; /* no match */
}

修正后运行测试代码会正常输出0，即目标值3在数组的下标0位置。

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