A small problem of binary search -- caused by python rounding

In the process of looking at the algorithm diagram, I learned a lot of algorithm knowledge, but also encountered a small problem in the middle.
Let's take a look at how to solve this small problem.
Here is the source code of 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

When we run with the following data:

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

This can result in the following errors:

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

The above information means that the index type is wrong. The index must be of integer type instead of float type.
This is because the division in python, i.e. "/", automatically converts types. Converts numbers that cannot be divisible to floating-point types.
Here are the solutions I came up with at the beginning:

def binary_search(list, item):
    low =  0
    high = len(list)
    while low <= high:
        mid = int((low + high) / 2)  # Add a type conversion to the result
        guess = list[mid]
        if guess == item:
            return mid
        if guess > item:
            high = mid - 1
        else:
            low = mid - 1
    return None

But when tested with the following data:

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

The result is that the cycle doesn't stop.
To find out what the problem is. Let's add a pirnt statement in the loop body to output the mid

def binary_search(list, item):
    low =  0
    high = len(list)
    while low <= high:
        mid = int((low + high) / 2)  # Add a type conversion to the result
        print(mid)
        guess = list[mid]
        if guess == item:
            return mid
        if guess > item:
            high = mid - 1
        else:
            low = mid - 1
    return None

Use the data above to run it.
It can be seen in the terminal that output 3 is looping all the time.
The reason for this problem is that int() is not the rounding operation we understand, but simply intercepts the integer part.
Look at the following example.

a = 5.4
b = 5.5
c = 5.6
print(int(a))
print(int(b))
print(int(c))

The output after operation is:

5
5
5

To solve this problem, we only need to add a 0.5 to the number to be rounded.
The above example is modified as follows:

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

The output after operation is:

5
6
6

So the above binary search can also be modified to:

def binary_search(list, item):
    low =  0
    high = len(list)
    while low <= high:
        mid = int((low + high) / 2 + 0.5)  # To achieve rounding, add a 0.5
        guess = list[mid]
        if guess == item:
            return mid
        if guess > item:
            high = mid - 1
        else:
            low = mid - 1
    return None

This solves the small problem in binary search.

Tags: Python

Posted on Sat, 09 Nov 2019 11:36:58 -0800 by alpinec