In the process of looking at the algorithm diagram, I learned a lot of algorithm knowledge, but I also encountered a small problem in the middle. Let’s take a look at how this small problem is solved. Here is the source code from the book:

def binary_search(list, item):
    low =  0
    high = len(list)
    while low <= high:
        mid = (low + high) / 2
        guess = list[mid]
        if guess == item:
            return mid
        if guess > item:
            high = mid - 1
        else:
            low = mid - 1
    return None
Copy the code

When we run with the following data:

list = [1, 2, 3, 4, 5]
item = 3
position = binary_search(list, item)
print(position)
Copy the code

Causes the following error:

Traceback (most recent call last) :File "binary_search.py", line 17.in <module>
    position = binary_search(list, item)
  File "binary_search.py", line 6.in binary_search
    guess = list[mid]
TypeError: list indices must be integers or slices, not float
Copy the code

The index must be an integer, not a float. This is because division, or “/”, converts the type automatically in Python. Converts a number that is not divisible to a floating point type. Here’s the solution I initially came up with:

def binary_search(list, item): low = 0 high = len(list) while low <= high: Mid = int((low + high) / 2)/mid = list[mid] if == item: return mid if > item: high = mid - 1 else: low = mid - 1 return NoneCopy the code

But when tested with the following data:

list = [1, 2, 3, 4, 5]
item = 5
position = binary_search(list, item)
print(position)
Copy the code

The result is that the cycle doesn’t stop. To find out what went wrong. Let’s add a pirnt statement to the body of the loop to output mid

def binary_search(list, item): low = 0 high = len(list) while low <= high: Print (mid) guess = list[mid] if guess == item: return mid if guess > item: high = mid - 1 else: low = mid - 1 return NoneCopy the code

Let’s run it with the data above. You can see in the terminal that it’s looping out 3 all the time. The reason why this is a problem is that the int() operation is not a round, as we understand it, but a simple interception of an integer. Look at the following example.

a = 5.4
b = 5.5
c = 5.6
print(int(a))
print(int(b))
print(int(c))
Copy the code

After running, the output is:

5 5Copy the code

To solve this problem we simply add a 0.5 to the number to be rounded. Change the above example to:

a = 5.4
b = 5.5
c = 5.6
print(int(a + 0.5))
print(int(b + 0.5))
print(int(c + 0.5))
Copy the code

After running, the output is:

5 June 6Copy the code

So the binary search above can also be changed to:

def binary_search(list, item): low = 0 high = len(list) while low <= high: Mid = int((low + high) / 2 + 0.5) # Mid = list[mid] if guess == item: return mid if guess > item: high = mid - 1 else: low = mid - 1 return NoneCopy the code

So that solves this little problem in binary search.