溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
本文小編為大家詳細介紹“Python查找算法如何實現”，內容詳細，步驟清晰，細節處理妥當，希望這篇“Python查找算法如何實現”文章能幫助大家解決疑惑，下面跟著小編的思路慢慢深入，一起來學習新知識吧。
查找算法是用來檢索序列數據（群體）中是否存在給定的數據（關鍵字），常用查找算法有：
線性查找：線性查找也稱為順序查找，用于在無序數列中查找。
二分查找：二分查找也稱為折半查找，其算法用于有序數列。
插值查找：插值查找是對二分查找算法的改進。
分塊查找：又稱為索引順序查找，它是線性查找的改進版本。
樹表查找：樹表查找又可分二叉查找樹、平衡二叉樹查找。
哈希查找：哈希查找可以直接通過關鍵字查找到所需要數據。
因樹表查找、哈希查找的所需篇幅較多，就不在本文講解。本文將詳細介紹除樹表、哈希之外的查找算法，并分析每一種算法的優點和缺點，并提出相應的優化方案。
線性查找也稱為順序查找，線性查找屬于原始、窮舉、暴力查找算法。容易理解、編碼實現也簡單。但是在數據量較多時，因其算法思想是樸素、窮舉的，算法中沒有太多優化設計，性能會很低下。
線性查找思想：
從頭至尾逐一掃描原始列表中的每一個數據，并和給定的關鍵字進行比較。
如果比較相等，則查找成功。
當掃描結束后，仍然沒有找到與給定關鍵字相等的數據，則宣布查找失敗。
根據線性查找算法的描述，很容易編碼實現：
'''
線性查找算法
參數：
nums: 序列
key:關鍵字
返回值：
關鍵字在序列中的位置
如果沒有，則返回 -1
'''
def line_find(nums, key):
for i in range(len(nums)):
if nums[i] == key:
return i
return -1
'''
測試線性算法
'''
if __name__ == "__main__":
nums = [4, 1, 8, 10, 3, 5]
key = int(input("請輸入要查找的關鍵字："))
pos = line_find(nums, key)
print("關鍵字 {0} 在數列的第 {1} 位置".format(key, pos))
'''
輸出結果：
請輸入要查找的關鍵字：3
關鍵字 3 在數列的 4 位置
'''線性查找算法的平均時間復雜度分析。
1.運氣最好的情況：如果要查找的關鍵字恰好在數列的第 1 個位置，則只需要查找 1 次就可以了。
如在數列=[4,1,8,10,3,5]中查找關鍵字 4 。
只需要查找 1 次。
2.運氣最不好的情況：一至掃描到數列最尾部時，才找到關鍵字。
如在數列=[4,1,8,10,3,5]中查找是否存在關鍵字 5 。
則需要查找的次數等于數列的長度，此處即為 6 次。
3.運氣不好不壞：如果要查找的關鍵字在數列的中間某個位置，則查找的概率是 1/n 。
n 為數列長度。
線性查找的平均查找次數應該=(1+n)/2。換成大 O 表示法則為 O(n) 。
大 O 表示法中忽視常量。
線性查找最糟糕情況是：掃描完整個數列后，沒有所要查找的關鍵字。
如在數列=[4,1,8,10,3,5]中查找是否存在關鍵字 12 。
掃描了 6 次后，鎩羽而歸！！
改良線性查找算法
可以對線性查找算法進行相應的優化。如設置“前哨站”。所謂“前哨站”，就是把要查找的關鍵字在查找之前插入到數列的尾部。
def line_find_(nums, key):
i = 0
while nums[i] != key:
i += 1
return -1 if i == len(nums)-1 else i
'''
測試線性算法
'''
if __name__ == "__main__":
nums = [4, 1, 8, 10, 3, 5]
key = int(input("請輸入要查找的關鍵字："))
# 查找之前，先把關鍵字存儲到列到的尾部
nums.append(key)
pos = line_find_(nums, key)
print("關鍵字 {0} 在數列的第 {1} 位置".format(key, pos))用"前哨站"優化后的線性查找算法的時間復雜度沒有變化，O(n)。或者說從 2 者代碼上看，也沒有太多變化。
但從代碼的實際運行角度而言，第 2 種方案減少了 if 指令的次數，同樣減少了編譯后的指令，也就減少了 CPU執行指令的次數，這種優化屬于微優化，不是算法本質上的優化。
使用計算機編程語言所編寫的代碼為偽指令代碼。
經過編譯后的指令代碼叫 CPU 指令集。
有一種優化方案就是減少編譯后的指令集。
二分查找屬于有序查找，所謂有序查找，指被查找的數列必須是有序的。如在數列=[4,1,8,10,3,5,12]中查找是否存在關鍵字 4 ，因數列不是有序的，所以不能使用二分查找，如果要使用二分查找算法，則需要先對數列進行排序。
二分查找使用了二分（折半）算法思想，二分查找算法中有 2 個關鍵信息需要隨時獲取：
一個是數列的中間位置 mid_pos。
一個是數列的中間值mid_val。
現在通過在數列 nums=[1,3,4,5,8,10,12] 中查找關鍵字 8來了解二分查找的算法流程。
在進行二分查找之前，先定義 2 個位置（指針）變量：
左指針 l_idx 初始指向數列的最左邊數字。
右指針 r_idx 初始指向數列的最右邊數字。
第 1 步：通過左、右指針的當前位置計算出數列的中間位置 mid_pos=3，并根據 mid_pos 的值找出數列中間位置所對應的值 mid_val=nums[mid_pos] 是 5。
二分查找算法的核心就是要找出數列中間位置的值。
第 2 步：把數列中間位置的值和給定的關鍵字相比較。這里關鍵字是 8，中間位置的值是 5，顯然 8 是大于 5，因為數列是有序的，自然會想到沒有必要再與數列中 5 之前的數字比較，而是專心和 5 之后的數字比較。
一次比較后再次查找的數列范圍縮小了一半。這也是二分算法的由來。
第 3 步：根據比較結果，調整數列的大小，這里的大小調整不是物理結構上調整，而是邏輯上調整，調整后原數列沒有變化。也就是通過修改左指針或右指針的位置，從邏輯上改變數列大小。調整后的數列如下圖。
二分查找算法中數列的范圍由左指針到右指針的長度決定。
第 4 步：重復上述步驟，至到找到或找不到為止。
編碼實現二分查找算法
''' 二分查找算法 ''' def binary_find(nums, key): # 初始左指針 l_idx = 0 # 初始在指針 r_ldx = len(nums) - 1 while l_idx <= r_ldx: # 計算出中間位置 mid_pos = (r_ldx + l_idx) // 2 # 計算中間位置的值 mid_val = nums[mid_pos] # 與關鍵字比較 if mid_val == key: # 出口一：比較相等，有此關鍵字，返回關鍵字所在位置 return mid_pos elif mid_val > key: # 說明查找范圍應該縮少在原數的左邊 r_ldx = mid_pos - 1 else: l_idx = mid_pos + 1 # 出口二：沒有查找到給定關鍵字 return -1 ''' 測試二分查找 ''' if __name__ == "__main__": nums = [1, 3, 4, 5, 8, 10, 12] key = 3 pos = binary_find(nums, key) print(pos)
通過前面對二分算法流程的分析，可知二分查找的子問題和原始問題是同一個邏輯，所以可以使用遞歸實現：
''' 遞歸實現二分查找 ''' def binary_find_dg(nums, key, l_idx, r_ldx): if l_idx > r_ldx: # 出口一：沒有查找到給定關鍵字 return -1 # 計算出中間位置 mid_pos = (r_ldx + l_idx) // 2 # 計算中間位置的值 mid_val = nums[mid_pos] # 與關鍵字比較 if mid_val == key: # 出口二：比較相等，有此關鍵字，返回關鍵字所在位置 return mid_pos elif mid_val > key: # 說明查找范圍應該縮少在原數的左邊 r_ldx = mid_pos - 1 else: l_idx = mid_pos + 1 return binary_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)
二分查找性能分析：
二分查找的過程用樹形結構描述會更直觀，當搜索完畢后，繪制出來樹結構是一棵二叉樹。
1.如上述代碼執行過程中，先找到數列中的中間數字 5，然后以 5 為根節點構建唯一結點樹。
2.5 和關鍵字 8 比較后，再在以數字 5 為分界線的右邊數列中找到中間數字10，樹形結構會變成下圖所示。
3.10 和關鍵字 8比較后，再在10 的左邊查找。
查找到8 后，意味著二分查找已經找到結果，只需要 3 次就能查找到最終結果。
從二叉樹的結構上可以直觀得到結論：二分查找關鍵字的次數由關鍵字在二叉樹結構中的深度決定。
4.上述是查找給定的數字8，為了能查找到數列中的任意一個數字，最終完整的樹結構應該如下圖所示。
很明顯，樹結構是標準的二叉樹。從樹結構上可以看出，無論查找任何數字，最小是 1 次，如查找數字 5，最多也只需要 3 次，比線性查找要快很多。
根據二叉樹的特性，結點個數為 n 的樹的深度為 h=log2(n+1)，所以二分查找算法的大 O 表示的時間復雜度為 O(logn)，是對數級別的時間度。
當對長度為1000的數列進行二分查找時，所需次數最多只要 10 次，二分查找算法的效率顯然是高效的。
但是，二分查找需要對數列提前排序，前面的時間復雜度是沒有考慮排序時間的。所以，二分查找一般適合數字變化穩定的有序數列。
插值查找本質是二分查找，插值查找對二分查找算法中查找中間位置的計算邏輯進行了改進。
原生二分查找算法中計算中間位置的邏輯：中間位置等于左指針位置加上右指針位置然后除以 2。
# 計算中間位置 mid_pos = (r_ldx + l_idx) // 2
插值算法計算中間位置邏輯如下所示：
key 為要查找的關鍵字！！
# 插值算法中計算中間位置 mid_pos = l_idx + (key - nums[l_idx]) // (nums[r_idx] - nums[l_idx]) * (r_idx - l_idx)
編碼實現插值查找：
# 插值查找基于二分法，只是mid計算方法不同
def binary_search(nums, key):
l_idx = 0
r_idx = len(nums) - 1
old_mid = -1
mid_pos = None
while l_idx < r_idx and nums[0] <= key and nums[r_idx] >= key and old_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
if nums[mid_pos] == key:
return "index is {}, target value is {}".format(mid_pos, nums[mid_pos])
# 此時目標值在中間值右邊，更新左邊界位置
elif nums[mid_pos] < key:
l_idx = mid_pos + 1
# 此時目標值在中間值左邊，更新右邊界位置
elif nums[mid_pos] > key:
r_idx = mid_pos - 1
return "Not find"
li =[1, 3, 4, 5, 8, 10, 12]
print(binary_search(li, 6))插值算法的中間位置計算時，對中間位置的計算有可能多次計算的結果是一樣的，此時可以認為查找失敗。
插值算法的性能介于線性查找和二分查找之間。
當數列中數字較多且分布又比較均勻時，插值查找算法的平均性能比折半查找要好的多。如果數列中數據分布非常不均勻，此種情況下插值算法并不是最好的選擇。
分塊查找類似于數據庫中的索引查詢，所以分塊查找也稱為索引查找。其算法的核心還是線性查找。
現有原始數列 nums=[5,1,9,11,23,16,12,18,24,32,29,25]，需要查找關鍵字11 是否存在。
第 1 步：使用分塊查找之前，先要對原始數列按區域分成多個塊。至于分成多少塊，可根據實際情況自行定義。分塊時有一個要求，前一個塊中的最大值必須小于后一個塊的最小值。
塊內部無序，但要保持整個數列按塊有序。
分塊查找要求原始數列從整體上具有升序或降序趨勢，如果數列的分布不具有趨向性，如果仍然想使用分塊查找，則需要進行分塊有序調整。
第 2 步：根據分塊信息，建立索引表。索引表至少應該有 2 個字段，每一塊中的最大值數字以及每一塊的起始地址。顯然索引表中的數字是有序的。
第 3 步：查找給定關鍵字時，先查找索引表，查詢關鍵字應該在那個塊中。如查詢關鍵字 29，可知應該在第三塊中，然后根據索引表中所提供的第三塊的地址信息，再進入第三塊數列，按線性匹配算法查找29 具體位置。
編碼實現分塊查找：
先編碼實現根據分塊數量、創建索引表，這里使用二維列表保存儲索引表中的信息。
''' 分塊：建立索引表 參數： nums 原始數列 blocks 塊大小 ''' def create_index_table(nums, blocks): # 索引表使用列表保存 index_table = [] # 每一塊的數量 n = len(nums) // blocks for i in range(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) return index_table ''' 測試分塊 ''' nums = [5, 1, 9, 11, 23, 16, 12, 18, 24, 32, 29, 25] it = create_index_table(nums, 3) print(it) ''' 輸出結果： [[11, 0, 3], [23, 4, 7], [32, 8, 11]] '''
代碼執行后，輸出結果和分析的結果一樣。
以上代碼僅對整體趨勢有序的數列進行分塊。如果整體不是趨向有序，則需要提供相應塊排序方案，有興趣者自行完成。
如上代碼僅為說明分塊查找算法。
分塊查找的完整代碼：
'''
分塊：建立索引表
參數：
nums 原始數列
blocks 塊大小
'''
def create_index_table(nums, blocks):
# 索引表使用列表保存
index_table = []
# 每一塊的數量
n = len(nums) // blocks
for i in range(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)
return index_table
'''
使用線性查找算法在對應的塊中查找
'''
def lind_find(nums, start, end):
for i in range(start, end):
if key == nums[i]:
return i
break
return -1
'''
測試分塊
'''
nums = [5, 1, 9, 11, 23, 16, 12, 18, 24, 32, 29, 25]
key = 16
# 索引表
it = create_index_table(nums, 3)
# 索引表的記錄編號
pos = -1
# 在索引表中查詢
for n in range(len(it) - 1):
# 是不是在第一塊中
if key <= it[0][0]:
pos = 0
# 其它塊中
if it[n][0] < key <= it[n + 1][0]:
pos = n + 1
break
if pos == -1:
print("{0} 在 {1} 數列中不存在".format(key, nums))
else:
idx = lind_find(nums, it[pos][1], it[pos][2] + 1)
if idx != -1:
print("{0} 在 {1} 數列的 {2} 位置".format(key, nums, idx))
else:
print("{0} 在 {1} 數列中不存在".format(key, nums))
'''
輸出結果
16 在 [5, 1, 9, 11, 23, 16, 12, 18, 24, 32, 29, 25] 數列的第 5 位置
'''分塊查找對于整體趨向有序的數列，其查找性能較好。但如果原始數列整體不是有序，則需要提供塊排序算法，時間復雜度沒有二分查找算法好。
分塊查找需要建立索引表，這也需要額外的存儲空間，其空間復雜度較高。其優于二分的地方在于只需要對原始數列進行部分排序。本質還是以線性查找為主。
讀到這里，這篇“Python查找算法如何實現”文章已經介紹完畢，想要掌握這篇文章的知識點還需要大家自己動手實踐使用過才能領會，如果想了解更多相關內容的文章，歡迎關注億速云行業資訊頻道。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
