StrikeW StrikeW - 2 months ago 13
C Question

C: Two different binary search implementation, one stuck in infinite loop

Here are two implementation of "forgetful" binary search, since they don't check for the exact match until they're finished.

1)

int bsearch1(int A[], int n, int target)
{
int low = 0, high = n - 1, mid = 0;
while (low < high)
{
mid = (low + high) >> 1;
if (target > A[mid])
low = mid + 1;
else
high = mid;
}
if (low == high)
{
if (A[low] == target)
return low;
}

return -1;
}


2)

int bsearch2(int A[], int n, int target)
{
int low = 0, high = n - 1, mid = 0;
while (low < high)
{
mid = (low + high) >> 1;
if (target < A[mid])
high = mid - 1;
else
low = mid;
}
if (low == high)
{
if (A[low] == target)
return low;
}

return -1;
}


NOTES:
n
is the length of array A,
target
is the element to find.

bsearch1
works fine, but
bsearch2
runs into infinite loop, e.g A=[1,3,5,6], target=5. The diff between them is the conditional statement in while loop, the one in
bsearch2
is just the opposite of
bsearch1
. Both are perfectly right in logic. How can I know in advance
bsearch2
is "wrong"? Can any one prove that the conditional statement in
bsearch2
will lead to infinite loop (maybe in a mathematic view)? I can't find any clues and evidences until now.

EDIT:
I have evaluated the whole process of the example A=[1,3,5,6], target=5:

1.low = 0, high = 3, mid = 1, A[mid] = 3

2.low = 1, high = 3, mid = 2, A[mid] = 5

3.low = 2, high = 3, mid = 2, A[mid] = 5

...

n.low = 2, high = 3, mid = 2, A[mid] = 5

I found that
bsearch2
can not reach to
low == high
this condition, thus can not exit the while loop. But I don't know why
low
and
high
can not reach to
low == high
in the end likes
bsearch1
.

Answer

Your second algorithm suffers from a repeating cycle as soon as you encounter a partition where high == (low+1). When that happens, you essentially have mid = (low + low + 1)/2, which is equivalent to (2*low)/2 + 1/2. With integer division, this results in mid = low + 0. Since your only movement on the low side is low = mid, but they're already equivalent, you have an infinite loop.

The reason this does not happen on the first implementation is the direction of the integer division loss. It is always down. Therefore high moving down does not suffer from this, and in-fact actually takes advantage of it.

To account for this in bsearch2 the same way bsearch1 takes advantage of the natural low-direction bias, the disgruntled rounding has to be accounted for in the mid-point calculation so it always moves in favor of the high-side. To do that, force the error out by biasing the calculation in the opposite direction. I.e. for bsearch2, do this:

mid = (low + high + 1) >> 1;

and truth be told, to avoid overflow, this really should be

mid = low + ((high - low + 1) >> 1);

This will achieve the same effect adjusting bsearch2 midpoints that bsearch1 does. An example is worth noting:

#include <stdio.h>

int bsearch2(int A[], int n, int target)
{
    int low = 0, high = n - 1, mid = 0;
    while (low < high)
    {
        mid = low + ((high - low + 1) >> 1);
        if (target < A[mid])
            high = mid - 1;
        else
            low = mid;
    }
    if (low == high)
    {
        if (A[low] == target)
            return low;
    }

    return -1;
}

int main()
{
    // build a sorted array from 1...20
    int A[20];
    for (int i=0; i<sizeof(A)/sizeof(*A); ++i)
        A[i] = i+1;

    for (int i=0; i<=sizeof(A)/sizeof(*A)+1; ++i)
        printf("Search for %d found index %d\n", i, bsearch2(A, sizeof(A)/sizeof(*A), i));

    return 0;
}

Output

Search for 0 found index -1
Search for 1 found index 0
Search for 2 found index 1
Search for 3 found index 2
Search for 4 found index 3
Search for 5 found index 4
Search for 6 found index 5
Search for 7 found index 6
Search for 8 found index 7
Search for 9 found index 8
Search for 10 found index 9
Search for 11 found index 10
Search for 12 found index 11
Search for 13 found index 12
Search for 14 found index 13
Search for 15 found index 14
Search for 16 found index 15
Search for 17 found index 16
Search for 18 found index 17
Search for 19 found index 18
Search for 20 found index 19
Search for 21 found index -1

I hope that made sense.