一個二分查找的小問題--由python四舍五入引起

harriszh 發(fā)布于2019-07-31 10:25 / 1179人閱讀

摘要：出現(xiàn)這個問題原因就處在這個取整的操作他不是我們理解的四舍五入，而是簡單的截取整數(shù)部分。上面的例子修改為運行后輸出為所以上面的二分查找也就可以修改成為了實現(xiàn)四舍五入加上一個這樣解決了二分查找中的這個小問題。

在看算法圖解的過程了解到了很多算法的知識，但在中間也遇到了一個小問題。
下面我們就看一下這個小問題時怎么解決的。
下面是書中的源碼：

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

當(dāng)我們用下面的數(shù)據(jù)運行時:

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

會導(dǎo)致如下錯誤：

Traceback (most recent call last):
  File "binary_search.py", line 17, in 
    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

上面信息的意思是索引類型錯誤，索引必須為整型而不是float型。
這是因為python中除法即“/”會自動轉(zhuǎn)換類型。將無法整除的數(shù)字轉(zhuǎn)換成浮點型。
下面是我一開始想到的解決辦法：

def binary_search(list, item):
    low =  0
    high = len(list)
    while low <= high:
        mid = int((low + high) / 2)  # 將結(jié)果加一個類型轉(zhuǎn)換即可
        guess = list[mid]
        if guess == item:
            return mid
        if guess > item:
            high = mid - 1
        else:
            low = mid - 1
    return None

但當(dāng)使用下面的數(shù)據(jù)進行測試時：

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

結(jié)果就是循環(huán)不會停止了。
為了找到問題出在哪里。我們在循環(huán)體中加一個pirnt語句輸出一下mid

def binary_search(list, item):
    low =  0
    high = len(list)
    while low <= high:
        mid = int((low + high) / 2)  # 將結(jié)果加一個類型轉(zhuǎn)換即可
        print(mid)
        guess = list[mid]
        if guess == item:
            return mid
        if guess > item:
            high = mid - 1
        else:
            low = mid - 1
    return None

還是使用上面的數(shù)據(jù)運行一下。
可以在終端中看到一直在循環(huán)輸出3。
出現(xiàn)這個問題原因就處在int() 這個取整的操作他不是我們理解的四舍五入，而是簡單的截取整數(shù)部分。
看下面的例子。

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

運行后輸出為：

5
5
5

為了解決這個問題我們只需要給要取整的數(shù)加一個0.5即可。
上面的例子修改為：

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

運行后輸出為：

5
6
6

所以上面的二分查找也就可以修改成：

def binary_search(list, item):
    low =  0
    high = len(list)
    while low <= high:
        mid = int((low + high) / 2 + 0.5)  # 為了實現(xiàn)四舍五入加上一個0.5
        guess = list[mid]
        if guess == item:
            return mid
        if guess > item:
            high = mid - 1
        else:
            low = mid - 1
    return None

這樣解決了二分查找中的這個小問題。