Ben Ben - 1 month ago 12
Python Question

Some cases cause my binary search to enter into an Infinite loop

I'm stuck in an infinite loop when searching for anything that is not in the list (but within the range of the list) and anything that is greater than the highest number. For example, when searching for 2 in the list

[1,2,5,6]
, my function returns index 1, which is correct. If I search for -1, it returns
False
which is correct. However, if I search for 100 or 4, it gets stuck in an infinite loop.

def binary_search(a_list, item):

if not a_list:
return False

mid = len(a_list)//2

print "Middle is: {}".format(a_list[mid])
print a_list


while len(a_list) > 0:
if a_list[mid] == item:
return mid
elif a_list[mid] > item:
return binary_search(a_list[:mid], item)
elif a_list[mid] < item:
return binary_search(a_list[mid:], item) + mid
else:
return False

a = binary_search([1, 2, 3, 4, 6, 7, 8], 5) # infinite loop
b = binary_search([1, 2, 3, 4, 6, 7, 8], 100) # infinite loop
c = binary_search([1, 2, 3, 4, 6, 7, 8], 8) # works correctly
d = binary_search([1, 2, 3, 4, 6, 7, 8], -2) # works correctly

Answer

Here is the code I used to examine your program. pdb allows you to step through the code one command at a time using s or continue to the next pdb.set_trace() using c. You use it like this:

import pdb

def binary_search(a_list, item):

    if not a_list:
        return False

    mid = len(a_list)//2

    print "Middle is: {}".format(a_list[mid])
    print a_list


    print a_list, item
    pdb.set_trace()

    while len(a_list) > 0:
        if a_list[mid] == item:
            return mid
        elif a_list[mid] > item:
            return binary_search(a_list[:mid], item)
        elif a_list[mid] < item:
            return binary_search(a_list[mid:], item) + mid
        else:
            return False

Now, there are a number of problems with your program, most notably the combination of looping and recursion. That is rarely correct. I will also point out that every case in your while loop has a return statement, so the while loop only has the effect of causing a search with a list size of 0 to return nothing at all. I doubt this is what you want.

The second problem is with you trying to return either the index of mid or False. There is no problem with what you're trying to do. The problem is with adding binary_search(...) to mid. The reason this is bad is that in Python, False evaluates to 0 when you use it like a number. Try running these in an interpreter:

False * 5 # => 0
False + 5 # => 5
False == 0 # => True
False is 0 # => False

This means that if your code worked otherwise and there was an unsuccessful search, you would still end up returning an integer answer a lot of the time. The False value would be lost in the addition to mid. To avoid this, the code I give below does not use recursion, so a return False is final. It goes directly to whoever called binary_search in the first place and not to any previous recursive calls. You could still write a recursive solution, but you would almost certainly need to have a comparison like if binary_search(...) is False: somewhere in your code then you would need to worry about the difference between is and == then you might be tempted to use is more frequently, which is a bad idea.

I also believe there are also some issues with a_list[mid:]. I did not confirm this, but I think you would want a_list[mid+1:] to exclude the middle element which you've confirmed is not the element you're looking for. Either way, the alternative code I have does not use slicing at all so I am not going to worry about it.

Here is the code which I believe does what you want.

def binary_search(a_list, item):

    if not a_list:
        return False

    mid = len(a_list)//2
    start = 0 # new and important
    end = len(a_list) # new and important

    while start < end: # new and important
        if a_list[mid] > item:
            end = mid
            mid = (end - start) // 2 # new and important
        elif a_list[mid] < item:
            start = mid + 1
            mid = start + (end - start) // 2 # new and important
        else:
            return mid

    return False

Note the removal of the recursive calls and the addition of start and end. These keep track of which part of the list you're searching in instead of the list slices you were using before.

Comments