# 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