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

Question

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

How do you call this function? What is the contents of the array, Is the array sorted (a requirement for binary search)? Have you tried to [*debug*](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/) your program? For example by using a [*debugger*](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems) to step through the code statement by statement while monitoring variables and their values. — Some programmer dude, May 18 '22 at 06:31
flag = binarySearch(p, n, key); if (flag == -1) { printf("The given key element %d is not found\n", key); } else { printf("The given key element %d is found at position : %d\n", key, flag); } — , May 18 '22 at 06:33
@JeevaniReddy How was my answer? Did you get Accepted? I am a competitive programmer as well and love getting Accepted. — Ryan Zhang, May 18 '22 at 06:36

score 5 · Answer 1 · answered May 18 '22 at 06:32

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.

score 1 · Answer 2 · answered May 18 '22 at 06:44

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

score 0 · Answer 3 · answered May 18 '22 at 06:37

0

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.

answered May 18 '22 at 06:37

nfries88

374
6
7

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

3 Answers3