成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

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

harriszh / 1190人閱讀

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

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

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ù)運(yùn)行時(shí):

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

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

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

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

def binary_search(list, item):
    low =  0
    high = len(list)
    while low <= high:
        mid = int((low + high) / 2)  # 將結(jié)果加一個(gè)類型轉(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ù)進(jìn)行測試時(shí)：

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

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

def binary_search(list, item):
    low =  0
    high = len(list)
    while low <= high:
        mid = int((low + high) / 2)  # 將結(jié)果加一個(gè)類型轉(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ù)運(yùn)行一下。
可以在終端中看到一直在循環(huán)輸出3。
出現(xiàn)這個(gè)問題原因就處在int() 這個(gè)取整的操作他不是我們理解的四舍五入，而是簡單的截取整數(shù)部分。
看下面的例子。

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

運(yùn)行后輸出為：

5
5
5

為了解決這個(gè)問題我們只需要給要取整的數(shù)加一個(gè)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))

運(yùn)行后輸出為：

5
6
6

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

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

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

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/43798.html

相關(guān)文章

  • Python基礎(chǔ)之(一)基本數(shù)據(jù)類型

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

    yagami 評論0 收藏0

  • 學(xué)Python說簡單真的簡單，說難也難，就由過來人給你總結(jié)為什么吧。

    摘要：數(shù)據(jù)科學(xué)其實(shí)就是機(jī)器學(xué)習(xí)，數(shù)據(jù)分析和數(shù)據(jù)可視化。機(jī)器學(xué)習(xí)通過實(shí)現(xiàn)算法，該算法能夠自動(dòng)檢測輸入中的模式。一般應(yīng)用于人臉識別語音識別熱門機(jī)器學(xué)習(xí)算法包括神經(jīng)網(wǎng)絡(luò)深度學(xué)習(xí)支持向量機(jī)隨機(jī)森林進(jìn)行數(shù)據(jù)分析可視化進(jìn)行數(shù)據(jù)可視化時(shí)，是非常熱門的庫。 ...

    HtmlCssJs 評論0 收藏0

  • 數(shù)據(jù)結(jié)構(gòu)與算法：二分查找

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

    zsirfs 評論0 收藏0

  • 數(shù)據(jù)結(jié)構(gòu)與算法：二分查找

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

    you_De 評論0 收藏0

  • 數(shù)據(jù)結(jié)構(gòu)與算法：二分查找

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

    gotham 評論0 收藏0

發(fā)表評論

0條評論

最新活動(dòng)
閱讀需要支付1元查看
<