Why is my non-recursive binary search function leading to an infinite loop?-CodePudding

Test case timed out. Possible infinite loop or inefficient algorithm used. The parameters can't be changed, some test cases are failing. Where am I going wrong?

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;
}

CodePudding user response：

You are not updating mid.

In each iteration of the binary search, mid should be updated to the midpoint of l and h, usually something like (l h)/2. However, as you have not updated mid, its value stays the same and runs forever.

This causes a Test case timed out.

CodePudding user response：

mid is not updated in the loop so if the loop does not exit at the first iteration, it will repeat the same tests for ever. The test framework stops the program after the maximum allowed time and reports a problem.

mid should be computed inside the loop.

Note also that the third test if (p[mid] > key) is redundant and could be replaced by an else clause:

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;
}

Note also that the index computed by the above function is not necessarily that of the first match in the array. Here is an alternative that will return the lowest index, can be used with an unsigned index type such as 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;
    }
}

CodePudding user response：

You never change mid. You're always testing the middle element of the array, rather than the midpoint between l and h. Move the assignment of mid into the loop.