溫馨提示×

您好，登錄后才能下訂單哦！

密碼登錄×
登錄注冊(cè)×
其他方式登錄
點(diǎn)擊 登錄注冊(cè) 即表示同意《億速云用戶服務(wù)條款》

Python中怎么實(shí)現(xiàn)二分查找

發(fā)布時(shí)間：2021-07-02 16:04:29 來源：億速云 閱讀：168 作者：Leah 欄目：大數(shù)據(jù)

這期內(nèi)容當(dāng)中小編將會(huì)給大家?guī)碛嘘P(guān)Python中怎么實(shí)現(xiàn)二分查找，文章內(nèi)容豐富且以專業(yè)的角度為大家分析和敘述，閱讀完這篇文章希望大家可以有所收獲。

二分查找

二分查找：從列表的中間開始比對(duì)

  • 若列表中間項(xiàng)正好就是目標(biāo)項(xiàng)，則查找結(jié)束，返回True

  • 若中間項(xiàng) > 目標(biāo)項(xiàng)：則只可能出現(xiàn)在前半部分

  • 若中間項(xiàng) < 目標(biāo)項(xiàng)：則只可能出現(xiàn)在后半部分

故每一次比對(duì)之后，都會(huì)將目標(biāo)項(xiàng)所在范圍縮小為原來的一般  ：  n/2

注意：有序表才能使用二分查找法

Python中怎么實(shí)現(xiàn)二分查找

Python中怎么實(shí)現(xiàn)二分查找  
 

二分查找：分而治之

二分查找算法實(shí)際上體現(xiàn)了解決問題的一種策略：分而治之

將原問題劃分為更小規(guī)模的小問題，每個(gè)小問題的解匯總后就是原問題的解

另一個(gè)有分而治之特點(diǎn)的算法是：遞歸

用遞歸也可以實(shí)現(xiàn)二分查找，基本結(jié)束條件是列表長度為0

Python中怎么實(shí)現(xiàn)二分查找

二分查找算法分析

由于二分查找每一次都會(huì)將下一步要比對(duì)的范圍縮小一半

Comparisons剩下的數(shù)據(jù)項(xiàng)個(gè)數(shù)
1
n/2
2
n/4
3n/8
……
……
i
n/2^i

上述就是小編為大家分享的Python中怎么實(shí)現(xiàn)二分查找了，如果剛好有類似的疑惑，不妨參照上述分析進(jìn)行理解。如果想知道更多相關(guān)知識(shí)，歡迎關(guān)注億速云行業(yè)資訊頻道。

向AI問一下細(xì)節(jié)

免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點(diǎn)不代表本網(wǎng)站立場，如果涉及侵權(quán)請(qǐng)聯(lián)系站長郵箱：is@yisu.com進(jìn)行舉報(bào)，并提供相關(guān)證據(jù)，一經(jīng)查實(shí)，將立刻刪除涉嫌侵權(quán)內(nèi)容。

AI
助
手