寫(xiě)在前面的話??

學(xué)了Python一些基礎(chǔ)知識(shí)之后,相信大家對(duì)Python使用方法有了一定的感悟,想要追求深層次的東西還要細(xì)細(xì)的學(xué)、慢慢的學(xué)。Python基礎(chǔ)教程更新到今天語(yǔ)法基礎(chǔ)算是完了,本專欄后續(xù)會(huì)對(duì)面向?qū)ο竽K更新。在進(jìn)行面向?qū)ο蟾轮澳貢?huì)有一步小插曲就是Python 百煉成鋼系列。主要的作用呢就是使用Python刷一刷算法題，使自己的基礎(chǔ)更加穩(wěn)固。在更新期間收到了廣大小伙伴的喜愛(ài),博主的知識(shí)水平也有所提升。下面呢咱們進(jìn)入正題講解今天咱們要學(xué)習(xí)的二分查找法。

問(wèn)題描述??

在學(xué)習(xí)一門語(yǔ)言的時(shí)候,咱們做的最多的一件事就是對(duì)數(shù)據(jù)進(jìn)行增刪改查,而對(duì)于增刪改查操作中最常做的就是查,因?yàn)橐粋€(gè)軟件主要的作用就是對(duì)親愛(ài)的用戶進(jìn)行信息展示,只有少部分管理員或者擁有權(quán)限的用戶才可以操作數(shù)據(jù)。比如在鏈表、數(shù)組中查找東西,咱們需要從頭開(kāi)始遍歷,挨個(gè)檢索。數(shù)據(jù)量龐大的時(shí)候會(huì)很令人頭疼。今天介紹的二分法查找(或稱折半查找) 主要是針對(duì)有序數(shù)列（也就是說(shuō)數(shù)據(jù)要先排序）。然后每次取中值進(jìn)行比較,依次折半縮小查找范圍。

原理分析??

1.實(shí)現(xiàn)步驟

• 1）確定該區(qū)間的中間位置K,在數(shù)組兩邊加上區(qū)間左右邊界l,r
• 2）將查找的值T與array[k]比較。若相等，查找成功返回此位置；否則確定新的查找區(qū)域，繼續(xù)二分查找。

區(qū)域確定如下：

• 每一次查找與中間值比較，判斷是否查找成功，不成功當(dāng)前查找區(qū)間將縮小一半。 視情況重新定左右邊界與中間索引k
• 時(shí)間復(fù)雜度為:O(log2n)。

2.圖解

圖片源于網(wǎng)絡(luò)

參考代碼??

這里在寫(xiě)代碼的時(shí)候?qū)Ρ攘讼到y(tǒng)內(nèi)置查找關(guān)鍵字in與二分法查找的運(yùn)行效果 打印結(jié)果如下：

由此可見(jiàn)Python底層的查找算法還是超級(jí)快的。使用起來(lái)也很方便

二分查找在本次實(shí)驗(yàn)中輸在了需要對(duì)列表進(jìn)行排序上

對(duì)于有序量大的數(shù)據(jù)就可以體現(xiàn)出來(lái)二分查找的優(yōu)勢(shì)了

import time,math,random

#計(jì)時(shí)器（使用的是函數(shù)裝飾器前面說(shuō)函數(shù)的時(shí)候提到過(guò)）
def timeT(func):
    def wapper(*s):
        start=time.perf_counter()
        judge=func(*s)
        end=time.perf_counter()
        return judge,start-end
    return wapper
# 使用內(nèi)置查找方法
@timeT
def serch1(lists,e):
    return e in lists

# 二分法
@ timeT
def serch2(lists,e):
    flag=False
    lists=sorted(lists)
    # print(lists)
    # 左游標(biāo)
    lo=0
    # 右游標(biāo)
    ma=len(lists)-1
    # 中間位置
    mid=len(lists)//2
    # 沒(méi)有在列表內(nèi)
    if lists[ma]<e:
        return False
    if lists[lo]>e:
        return False
    # 依次縮小左右游標(biāo)，直到lo>ma
    while lo<=ma:
        if lists[mid]>e:
            ma=mid
            mid=(lo+ma)//2
        elif lists[mid]<e:
            lo=mid
            mid=(lo+ma)//2
        else:
        	#標(biāo)記位,True代表查到了
            flag=True
            break
    return flag


def main():
	#生成一個(gè)含有10000個(gè)元素的列表
    numarr=[x for x in range(10000)]
    #打亂列表順序
    random.shuffle(numarr)
    print(*serch1(numarr,23))
    print(*serch2(numarr,223))
    print(223 in numarr)
    # print(numarr)

if __name__=="__main__":
    main()  

到此這篇關(guān)于Python真題案例之二分法查找詳解的文章就介紹到這了,更多相關(guān)Python 二分法查找內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論