Python查找算法如何實(shí)現(xiàn)

第Python查找算法如何實(shí)現(xiàn)print(pos)

通過前面對二分算法流程的分析，可知二分查找的子問題和原始問題是同一個邏輯，所以可以使用遞歸實(shí)現(xiàn)：

遞歸實(shí)現(xiàn)二分查找

defbinary_find_dg(nums,key,l_idx,r_ldx):

ifl_idxr_ldx:

#出口一：沒有查找到給定關(guān)鍵字

return-1

#計算出中間位置

mid_pos=(r_ldx+l_idx)//2

#計算中間位置的值

mid_val=nums[mid_pos]

#與關(guān)鍵字比較

ifmid_val==key:

#出口二：比較相等，有此關(guān)鍵字，返回關(guān)鍵字所在位置

returnmid_pos

elifmid_valkey:

#說明查找范圍應(yīng)該縮少在原數(shù)的左邊

r_ldx=mid_pos-1

else:

l_idx=mid_pos+1

returnbinary_find_dg(nums,key,l_idx,r_ldx)

測試二分查找

if__name__==__main__:

nums=[1,3,4,5,8,10,12]

key=8

pos=binary_find_dg(nums,key,0,len(nums)-1)

print(pos)

二分查找性能分析：

二分查找的過程用樹形結(jié)構(gòu)描述會更直觀，當(dāng)搜索完畢后，繪制出來樹結(jié)構(gòu)是一棵二叉樹。

1.如上述代碼執(zhí)行過程中，先找到數(shù)列中的中間數(shù)字5，然后以5為根節(jié)點(diǎn)構(gòu)建唯一結(jié)點(diǎn)樹。

2.5和關(guān)鍵字8比較后，再在以數(shù)字5為分界線的右邊數(shù)列中找到中間數(shù)字10，樹形結(jié)構(gòu)會變成下圖所示。

3.10和關(guān)鍵字8比較后，再在10的左邊查找。

查找到8后，意味著二分查找已經(jīng)找到結(jié)果，只需要3次就能查找到最終結(jié)果。

從二叉樹的結(jié)構(gòu)上可以直觀得到結(jié)論：二分查找關(guān)鍵字的次數(shù)由關(guān)鍵字在二叉樹結(jié)構(gòu)中的深度決定。

4.上述是查找給定的數(shù)字8，為了能查找到數(shù)列中的任意一個數(shù)字，最終完整的樹結(jié)構(gòu)應(yīng)該如下圖所示。

很明顯，樹結(jié)構(gòu)是標(biāo)準(zhǔn)的二叉樹。從樹結(jié)構(gòu)上可以看出，無論查找任何數(shù)字，最小是1次，如查找數(shù)字5，最多也只需要3次，比線性查找要快很多。

根據(jù)二叉樹的特性，結(jié)點(diǎn)個數(shù)為n的樹的深度為h=log2(n+1)，所以二分查找算法的大O表示的時間復(fù)雜度為O(logn)，是對數(shù)級別的時間度。

當(dāng)對長度為1000的數(shù)列進(jìn)行二分查找時，所需次數(shù)最多只要10次，二分查找算法的效率顯然是高效的。

然而，二分查找算法在實(shí)行之前需要對數(shù)列進(jìn)行排序，因此前面所述的時間復(fù)雜度并未包含排序所需的時間。所以，二分查找一般適合數(shù)字變化穩(wěn)定的有序數(shù)列。

3.插值查找

插值查找本質(zhì)是二分查找，插值查找對二分查找算法中查找中間位置的計算邏輯進(jìn)行了改進(jìn)。

原生二分查找算法中計算中間位置的邏輯：中間位置等于左指針位置加上右指針位置然后除以2。

#計算中間位置

mid_pos=(r_ldx+l_idx)//2

插值算法計算中間位置邏輯如下所示：

key為要查找的關(guān)鍵字！！

#插值算法中計算中間位置

mid_pos=l_idx+(key-nums[l_idx])//(nums[r_idx]-nums[l_idx])*(r_idx-l_idx)

編碼實(shí)現(xiàn)插值查找：

#插值查找基于二分法，只是mid計算方法不同

defbinary_search(nums,key):

l_idx=0

r_idx=len(nums)-1

old_mid=-1

mid_pos=None

whilel_idxr_idxandnums[0]=keyandnums[r_idx]=keyandold_mid!=mid_pos:

#中間位置計算

mid_pos=l_idx+(key-nums[l_idx])//(nums[r_idx]-nums[l_idx])*(r_idx-l_idx)

old_mid=mid_pos

ifnums[mid_pos]==key:

returnindexis{},targetvalueis{}.format(mid_pos,nums[mid_pos])

#此時目標(biāo)值在中間值右邊，更新左邊界位置

elifnums[mid_pos]key:

l_idx=mid_pos+1

#此時目標(biāo)值在中間值左邊，更新右邊界位置

elifnums[mid_pos]key:

r_idx=mid_pos-1

returnNotfind

li=[1,3,4,5,8,10,12]

print(binary_search(li,6))

插值算法的中間位置計算時，對中間位置的計算有可能多次計算的結(jié)果是一樣的，此時可以認(rèn)為查找失敗。

插值算法的性能介于線性查找和二分查找之間。

如果序列具有較大數(shù)量的均勻分布的數(shù)字，插值查找算法的平均執(zhí)行效率要比二分查找好得多。如果數(shù)據(jù)在數(shù)列中分布不均勻，插值算法并不是最優(yōu)選擇。

4.分塊查找

分塊查找類似于數(shù)據(jù)庫中的索引查詢，所以分塊查找也稱為索引查找。其算法的核心還是線性查找。

現(xiàn)有原始數(shù)列nums=[5,1,9,11,23,16,12,18,24,32,29,25]，需要查找關(guān)鍵字11是否存在。

第1步：使用分塊查找之前，先要對原始數(shù)列按區(qū)域分成多個塊。至于分成多少塊，可根據(jù)實(shí)際情況自行定義。分塊時有一個要求，前一個塊中的最大值必須小于后一個塊的最小值。

塊內(nèi)部無序，但要保持整個數(shù)列按塊有序。

分塊查找要求原始數(shù)列從整體上具有升序或降序趨勢，如果數(shù)列的分布不具有趨向性，如果仍然想使用分塊查找，則需要進(jìn)行分塊有序調(diào)整。

第2步：根據(jù)分塊信息，建立索引表。索引表至少應(yīng)該有2個字段，每一塊中的最大值數(shù)字以及每一塊的起始地址。顯然索引表中的數(shù)字是有序的。

第3步：查找給定關(guān)鍵字時，先查找索引表，查詢關(guān)鍵字應(yīng)該在那個塊中。如查詢關(guān)鍵字29，可知應(yīng)該在第三塊中，然后根據(jù)索引表中所提供的第三塊的地址信息，再進(jìn)入第三塊數(shù)列，按線性匹配算法查找29具體位置。

編碼實(shí)現(xiàn)分塊查找：

先編碼實(shí)現(xiàn)根據(jù)分塊數(shù)量、創(chuàng)建索引表，這里使用二維列表保存儲索引表中的信息。

分塊：建立索引表

nums原始數(shù)列

blocks塊大小

defcreate_index_table(nums,blocks):

#索引表使用列表保存

index_table=[]

#每一塊的數(shù)量

n=len(nums)//blocks

foriinrange(0,len(nums),n):

#索引表中的每一行記錄

tmp_lst=[]

#最大值

tmp_lst.append(max(nums[i:i+n-1]))

#起始地址

tmp_lst.append(i)

#終止地址

tmp_lst.append(i+n-1)

#添加到索引表中

index_table.append(tmp_lst)

returnindex_table

nums=[5,1,9,11,23,16,12,18,24,32,29,25]

it=create_index_table(nums,3)

print(it)

輸出結(jié)果：

[[11,0,3],[23,4,7],[32,8,11]]

代碼執(zhí)行后，輸出結(jié)果和分析的結(jié)果一樣。

以上代碼僅對整體趨勢有序的數(shù)列進(jìn)行分塊。如果整體沒有向有序趨勢發(fā)展，則需要提供適當(dāng)?shù)膲K排序計劃，有興趣的人可以自行完成。

如上代碼僅為說明分塊查找算法。

分塊查找的完整代碼：

分塊：建立索引表

nums原始數(shù)列

blocks塊大小

defcreate_index_table(nums,blocks):

#索引表使用列表保存

index_table=[]

#每一塊的數(shù)量

n=len(nums)//blocks