算法01 - 二分法查找

二分法查找簡(jiǎn)介
輸入:一個(gè)"有序"元素列表
輸出:返回要查找的元素位置,沒(méi)有這個(gè)元素則返回None

使用背景簡(jiǎn)介
假如有一個(gè)需求,在1-100順序排列的數(shù)中找到指定的數(shù)字N,我們能想到的辦法有:

方法(1), 在1開(kāi)始, 挨個(gè)詢問(wèn)是不是1,是不是2,..., 一直到指定的N,如果N是100的話,我們需要試驗(yàn)到第100次才能猜中,也就是說(shuō)在順序查找中,我們最多需要100次完成需求,假設(shè)試驗(yàn)一次需要0.001秒,試驗(yàn)100次找到指定數(shù)字,最多需要0.1秒. 俗話講: 拋開(kāi)數(shù)據(jù)規(guī)模和復(fù)雜度談算法,純屬耍流氓! 如果我們面對(duì)的是10億個(gè)數(shù)字, 在里面查找指定數(shù)字,最多需要10億*0.001秒 = 100萬(wàn)秒≈277小時(shí)

方法(2), 面對(duì)1-100, 首先最大化的排除無(wú)用數(shù)據(jù), 先猜是不是50, 是就返回, 不是返回50是大了還是小了, 然后把50當(dāng)做上邊界或者下邊界, 再次猜中間位置, 這樣依次猜下去, 例如我們N=100,s1猜50小了, s2猜75, s3猜88, s4猜94, s5猜97, s6猜99, s7猜100共計(jì)7步找到結(jié)果, 如果是10億需要多少次呢? 答案是(\log_2 10億 )=30次

代碼實(shí)現(xiàn)

代碼截圖
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書(shū)系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

友情鏈接更多精彩內(nèi)容