寫在前面的話??

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

問題描述??

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

原理分析??

1.實現(xiàn)步驟

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

區(qū)域確定如下：

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

2.圖解

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

參考代碼??

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

由此可見Python底層的查找算法還是超級快的。使用起來也很方便

二分查找在本次實驗中輸在了需要對列表進行排序上

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

import time,math,random

#計時器（使用的是函數(shù)裝飾器前面說函數(shù)的時候提到過）
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)
    # 左游標
    lo=0
    # 右游標
    ma=len(lists)-1
    # 中間位置
    mid=len(lists)//2
    # 沒有在列表內(nèi)
    if lists[ma]<e:
        return False
    if lists[lo]>e:
        return False
    # 依次縮小左右游標，直到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:
        	#標記位,True代表查到了
            flag=True
            break
    return flag


def main():
	#生成一個含有10000個元素的列表
    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)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論