为什么我的非递归二分搜索函数会导致无限循环？

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的中点，通常类似于。但是，由于您尚未更新，因此其值保持不变并永远运行。lh(l+h)/2mid

这会导致测试用例超时。