CODEWITHSUNDEEP
python-3.xalgorithmbinary-search
J. Ochoa
J. Ochoa

Reputation: 25

In binary search, why is my loop infinite?

I run a while loop with a function to check if a variable i is higher than the len of the list. I placed it there as a way to stop the loop, but it does not check it. Since it doesn't end on it's own I had to place an if condition inside that returns false.

def binarySearch(numberlist, number):
    first = 0
    last = len(numberlist)-1
    found = False
    i=0

    while found == False or i <= len(numberlist):
        i = i + 1
        mid = (first + last) // 2
        print(numberlist[mid])
        if i > len(numberlist)+1:
            return False
        if mid < first or mid > last or mid < 0:
            return False
        if number == numberlist[mid] or number == numberlist[first] or number == numberlist[last] :
            return True
        elif number < numberlist[mid]:
            last = mid
        elif number > numberlist[mid]:
            first = mid
    return False

Upvotes: 1

Views: 65

Answers (1)

Olivier Melan&#231;on
Olivier Melan&#231;on

Reputation: 22294

The error lies in the following lines.

elif number < numberlist[mid]:
    last = mid
elif number > numberlist[mid]:
    first = mid

Consider the case where we are looking for a number which is not in the list.

The pointers first, last and mid will eventually all converge to some index. In that case one of the two last conditions will be True, but since all three values are already equal, the pointers are not updated anymore and we enter an infinite loop.

To makes sure this does not happen, we must make sure the interval always decreases in size by setting first to mid + 1 or last to mid - 1, depending on the condition. We can then stop looping if first becomes greater than last.

def binary_search(numberlist, number):
    first, last = 0, len(numberlist) - 1

    while first <= last:
        mid = (first + last) // 2
        if numberlist[mid] == number:
            return True
        elif numberlist[mid] > number:
            last = mid - 1
        else:
            first = mid + 1

    return False

Upvotes: 1

Related Questions