c - c中的二分搜索算法

Question

我正在尝试创建一个int find_pos(int item, int a[], int len)如下工作的函数：

t返回键的数组中的索引successor，k如果存在，则返回KEY_NOT_FOUND。

键t是 的后继，k如果是存储在其中t的最小键。sda->buffert >= k

const int KEY_NOT_FOUND = -1;

int find_pos(int item, int a[], int len) {
 int low = 0;
 int high = len-1;
 if (a[0] >= item && len == 1) {
 return 0;
 }
 if(a[0] < item && len == 1) {
 return KEY_NOT_FOUND;
 }
 while (low <= high) {
 int mid = low + (high - low) / 2;
 if (a[mid] == item) {
  return mid;
 } else if (a[mid] < item) {
   low = mid + 1;
 } else {
   high = mid - 1;
 }
 if(a[high] < item) {// invalid size read of 4
  return high + 1;
 }
 }
 return KEY_NOT_FOUND;
}

但是，它可能会导致无效的读取大小读取 4 在

if(a[high] < item)

有人可以解释（或举个例子）为什么这条线会导致无效的读取大小读取为 4？提前致谢。

Answer 1

假设low == high == 0while 循环的开始。

所以，mid == 0

然后代码确实high = mid - 1;如此，high现在是负数，并且a[high]是非法访问。