C语言 为什么我的非递归二分搜索函数导致无限循环?

Question

测试用例超时。可能使用了无限循环或低效的算法。 参数不能更改，一些测试用例失败。我哪里做错了?

int binarySearch(int p[], int n, int key) {
int l = 0, h = n - 1;
int mid = l + (h - l) / 2;
while (l <= h) {
if (p[mid] == key) {
return mid;
}
if (p[mid] < key) {
l = mid + 1;
}
if (p[mid] > key) {
h = mid - 1;
}
}
return -1;
}

Answer 1

您没有更新mid。

在二分查找的每次迭代中，mid应该更新到l和h的中点，通常是(l+h)/2。但是，由于您没有更新mid，它的值保持不变并永远运行。

这会导致测试用例超时。

Answer 2

mid在循环中没有更新，所以如果循环在第一次迭代时没有退出，它将永远重复相同的测试。测试框架在最大允许时间后停止程序并报告问题。

mid应在循环内计算。

还请注意，第三个测试if (p[mid] > key)是多余的，可以用else子句替换:

int binarySearch(int p[], int n, int key) {
int l = 0, h = n - 1;
while (l <= h) {
int mid = l + (h - l) / 2;
if (p[mid] == key) {
return mid;
}
if (p[mid] < key) {
l = mid + 1;
} else {
h = mid - 1;
}
}
return -1;
}

还要注意，上面函数计算的索引不一定是数组中第一个匹配项的索引。下面是返回最低索引的替代方法，可用于unsigned索引类型，如size_t:

int binarySearch(int p[], int n, int key) {
int lo = 0, hi = n;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (p[mid] < key) {
lo = mid + 1;
} else {
hi = mid;
}
}
if (lo < n && p[lo] == key) {
return lo;
} else {
return -1;
}
}

Answer 3

你永远不会改变mid，你总是测试数组的中间元素，而不是l和h之间的中点。将mid的赋值移到循环中。