Infinite loop in binary search algorithm-CodePudding

I'm a newbie in algorithms. I have recently started studying binary search and tryed to implement it on my own. The task is simple: we have an array of integers a and an integer x. If a contains x the result should be its index, otherwise the function should return -1.

Here is the code I have written:

def binary_search(a, x):
    l = 0
    r = len(a)
    while r - l > 0:
        m = (l   r) // 2
        if a[m] < x:
            l = m
        else:
            r = m
    if a[l] == x:
        return l
    return -1

But this code stucks in infinite cycle on a = [1, 2] and x = 2. I suppose, that I have incorrect cycle condition (probably, should be r - l >= 0), but this solution does not help. Where am I wrong?

CodePudding user response：

Let me do some desk checking. I'll assume a = [1, 2] and we are searching for a 2

So we start with

l = 0
r = 2

Since r - l = 2 > 0, we enter the while-loop.

m = (l   r) / 2 = (0   2) / 2 = 1
a[m] = a[1] = 2 == x  (hence not less than x)
r = m = 1 (and l remains the same)

Now r - l = 1 - 0 = 1 > 0, so we continue

m = (l   r) / 2 = (0   1) / 2 = 0
a[m] = a[0] = 1 < x
l = m = 0 (and r remains the same)

After this iteration both r and l have the same value as before, which then produces an endless loop.

Ashok's answer is a great fix. But I think it'll be educational to do some desk checking on the fixed code and look what improves it.

Basically the problematic situation arises, when l 1 = r. Then m will always evaluate to l, a[l] < x and l is set to m again, which doesn't change the situation.

In a larger piece of code it'll make sense to make a table that contains a column for each variable to watch and a column to write down the code line that was evaluated. A column for remarks won't harm either.

CodePudding user response：

As Mani mentioned you are not considering when A[m]==x. Include that case (at that point you've found a so just return m), and once you have that case we can let l=m 1 when we are still below x. Like this:

def binary_search(a, x):
    l = 0
    r = len(a)
    while r - l > 0:
        m = (l   r) // 2
        if a[m] < x:
            l = m   1
        elif a[m]==x:
            return m
        else:
            r = m
    if l<len(a) and a[l] == x:
        return l
    return -1