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

harriszh 發布于2019-07-31 10:25 / 1184人閱讀

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

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

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

當我們用下面的數據運行時:

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

會導致如下錯誤：

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中除法即“/”會自動轉換類型。將無法整除的數字轉換成浮點型。
下面是我一開始想到的解決辦法：

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

但當使用下面的數據進行測試時：

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

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

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

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

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

運行后輸出為：

5
5
5

為了解決這個問題我們只需要給要取整的數加一個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)  # 為了實現四舍五入加上一個0.5
        guess = list[mid]
        if guess == item:
            return mid
        if guess > item:
            high = mid - 1
        else:
            low = mid - 1
    return None

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

云服務器 GPU云服務器二分查找二分查找代碼二分法查找二分查找c語言實例

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/43798.html

Python基礎之(一)基本數據類型

摘要：但是在轉化中，浮點數轉化為二進制后，不會精確等于十進制的。一般情況下，只要簡單地將最終顯示的結果用四舍五入到所期望的十進制位數，就會得到期望的最終結果。四舍五入內建函數。在中的第二個數，表示要保留的小數位數，返回值是一個四舍五入之后的數值。數字基本類型首先，進入Python交互模式中： //整數 >>> 3 3 //長整數 >>> 3333333333333333333333...

yagami 2019-07-25 10:50 評論0 收藏0
學Python說簡單真的簡單，說難也難，就由過來人給你總結為什么吧。

摘要：數據科學其實就是機器學習，數據分析和數據可視化。機器學習通過實現算法，該算法能夠自動檢測輸入中的模式。一般應用于人臉識別語音識別熱門機器學習算法包括神經網絡深度學習支持向量機隨機森林進行數據分析可視化進行數據可視化時，是非常熱門的庫。 ...

HtmlCssJs 2021-11-11 16:55 評論0 收藏0
數據結構與算法：二分查找

摘要：為檢查長度為的列表，二分查找需要執行次操作。最后需要指出的一點是高水平的讀者可研究一下二叉樹關于二叉樹，戳這里數據結構與算法二叉樹算法常見練習在一個二維數組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。常見數據結構簡單數據結構（必須理解和掌握）有序數據結構：棧、隊列、鏈表。有序數據結構省空間（儲存空間小）無序數據結構：集合、字典、散列表，無序...

zsirfs 2019-08-23 15:33 評論0 收藏0
數據結構與算法：二分查找

摘要：為檢查長度為的列表，二分查找需要執行次操作。最后需要指出的一點是高水平的讀者可研究一下二叉樹關于二叉樹，戳這里數據結構與算法二叉樹算法常見練習在一個二維數組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。常見數據結構簡單數據結構（必須理解和掌握）有序數據結構：棧、隊列、鏈表。有序數據結構省空間（儲存空間小）無序數據結構：集合、字典、散列表，無序...

you_De 2019-08-16 15:26 評論0 收藏0
數據結構與算法：二分查找

摘要：為檢查長度為的列表，二分查找需要執行次操作。最后需要指出的一點是高水平的讀者可研究一下二叉樹關于二叉樹，戳這里數據結構與算法二叉樹算法常見練習在一個二維數組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。常見數據結構簡單數據結構（必須理解和掌握）有序數據結構：棧、隊列、鏈表。有序數據結構省空間（儲存空間小）無序數據結構：集合、字典、散列表，無序...

gotham 2019-07-31 10:07 評論0 收藏0