Ben - 1 year ago 64
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
``````

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.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download