Binary search with Python

Question

I was doing some experimentation by myself and I can't figure out where I am doing an error. I would like to have a binary function able to take a list (ascendent order) and able to find if a value is present in the selected list. The search must start from the middle of the list in order to save computational time. This is what I am trying to do, but when I start the function python starts working without an end. Here my code:
def binary(data, value):
low = 0
high = len(data) - 1    #Mind the -1!!
found = False
mid = int(len(data)/2)

while low <= high and not found:

if data[mid] == value:
        found = True
    else:
        if value < data[mid]:
            high = mid - 1
    #elif value > data[mid]:
        else:
            low = mid + 1
    #else:
    #   return "Error, something went wrong!"
if found:
    return low
else:
    return "Nada"
low and high are respectively lower and upper bounds of the list. Please help

jonlunsford · Answer

Stefano:
The problem I see is in your second if statement.
python
if value < data[mid]:

Let's say you pass in list containing 8 elements, then your calculation for mid will be equal to 4 (mid=4).  Now remember, you are using mid as an index.  So this code says continue if the value is less than the value of the element at index 4.  So far, so good.
Your next line of code:
python
high = mid - 1

In our example where mid=4, this would set high to 3.  If low is sill less than high it loops again.  Assuming the first if statement is false, then the code get's back to the if block above.  HERE IS THE PROBLEM.
'value' has not changed, nor has 'mid' changed, so this code executes again.  And since mid has not changed the second block of code remains unchanged as well.  In other words, high will always be 3, because mid is always 4.  Also, low never changes because you are still jumping in and out of this block.  You are now in an Infinite Loop.
In summary, you are using high and low as conditions for the loop, but you are comparing list elements using data[mid], but the mid value is fixed outside of the loop.  You might want to consider using list slicing.  Sometimes writing it out first in pseudocode will help.
 if value is less than the value at the mid point:
    create a new list from the lower half of the initial list
else:
    create a new list from the upper half of the initial list
 loop through the new list searching for value, or repeat and split the new list again
Hope this helps!

Welcome to the Treehouse Community

Looking to learn something new?

Stefano Nebiolo

Stefano Nebiolo

Binary search with Python

1 Answer

jonlunsford

jonlunsford