Python中有哪些常用的查找數據結構及算法？針對這個問題，這篇文章詳細介紹了相對應的分析和解答，希望可以幫助更多想解決這個問題的小伙伴找到更簡單易行的方法。

一、基本概念

查找（Searching）就是根據給定的某個值，在查找表中確定一個其關鍵字等于給定值的數據元素（或記錄）。

查找表（Search Table）：由同一類型的數據元素（或記錄）構成的集合
關鍵字（Key）：數據元素中某個數據項的值，又稱為鍵值。
主鍵（Primary Key）：可唯一地標識某個數據元素或記錄的關鍵字。

查找表按照操作方式可分為：

靜態查找表（Static Search Table）：只做查找操作的查找表。它的主要操作是：查詢某個“特定的”數據元素是否在表中檢索某個“特定的”數據元素和各種屬性動態查找表（Dynamic Search Table）：在查找中同時進行插入或刪除等操作：查找時插入數據查找時刪除數據

二、無序表查找

也就是數據不排序的線性查找，遍歷數據元素。
算法分析：最好情況是在第一個位置就找到了，此為O(1)；最壞情況在最后一個位置才找到，此為O(n)；所以平均查找次數為(n+1)/2。最終時間復雜度為O(n)

#最基礎的遍歷無序列表的查找算法#時間復雜度O(n)
defsequential_search(lis,key):
length=len(lis)
foriinrange(length):
iflis[i]==key:
returni
else:
returnFalse
if__name__=='__main__':
LIST=[1,5,8,123,22,54,7,99,300,222]
result=sequential_search(LIST,123)
print(result)

三、有序表查找

查找表中的數據必須按某個主鍵進行某種排序！

1. 二分查找(Binary Search)

算法核心：在查找表中不斷取中間元素與查找值進行比較，以二分之一的倍率進行表范圍的縮小。

#針對有序查找表的二分查找算法#時間復雜度O(log(n))
defbinary_search(lis,key):
low=0
high=len(lis)-1
time=0
whilelow<high:
time+=1
mid=int((low+high)/2)ifkey<lis[mid]:
high=mid-1
elifkey>lis[mid]:
low=mid+1
else:#打印折半的次數
print("times:%s"%time)returnmid
print("times:%s"%time)returnFalseif__name__=='__main__':
LIST=[1,5,7,8,22,54,99,123,200,222,444]
result=binary_search(LIST,99)
print(result)

2. 插值查找

二分查找法雖然已經很不錯了，但還有可以優化的地方。
有的時候，對半過濾還不夠狠，要是每次都排除十分之九的數據豈不是更好？選擇這個值就是關鍵問題，插值的意義就是：以更快的速度進行縮減。

插值的核心就是使用公式：
value = (key - list[low])/(list[high] - list[low])

用這個value來代替二分查找中的1/2。
上面的代碼可以直接使用，只需要改一句。

#插值查找算法#時間復雜度O(log(n))
defbinary_search(lis,key):
low=0
high=len(lis)-1
time=0
whilelow<high:
time+=1
#計算mid值是插值算法的核心代碼
mid=low+int((high-low)*(key-lis[low])/(lis[high]-lis[low]))
print("mid=%s,low=%s,high=%s"%(mid,low,high))ifkey<lis[mid]:
high=mid-1
elifkey>lis[mid]:
low=mid+1
else:#打印查找的次數
print("times:%s"%time)returnmid
print("times:%s"%time)returnFalseif__name__=='__main__':
LIST=[1,5,7,8,22,54,99,123,200,222,444]
result=binary_search(LIST,444)
print(result)

插值算法的總體時間復雜度仍然屬于O(log(n))級別的。其優點是，對于表內數據量較大，且關鍵字分布比較均勻的查找表，使用插值算法的平均性能比二分查找要好得多。反之，對于分布極端不均勻的數據，則不適合使用插值算法。

3. 斐波那契查找

由插值算法帶來的啟發，發明了斐波那契算法。其核心也是如何優化那個縮減速率，使得查找次數盡量降低。
使用這種算法，前提是已經有一個包含斐波那契數據的列表
F = [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,...]

#斐波那契查找算法#時間復雜度O(log(n))deffibonacci_search(lis,key):
#需要一個現成的斐波那契列表。其最大元素的值必須超過查找表中元素個數的數值。
F=[1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368]
low=0
high=len(lis)-1

#為了使得查找表滿足斐波那契特性，在表的最后添加幾個同樣的值
#這個值是原查找表的最后那個元素的值
#添加的個數由F[k]-1-high決定
k=0
whilehigh>F[k]-1:
k+=1
print(k)
i=highwhileF[k]-1>i:
lis.append(lis[high])
i+=1
print(lis)
#算法主邏輯。time用于展示循環的次數。
time=0
whilelow<=high:
time+=1
#為了防止F列表下標溢出，設置if和else
ifk<2:
mid=lowelse:
mid=low+F[k-1]-1

print("low=%s,mid=%s,high=%s"%(low,mid,high))ifkey<lis[mid]:
high=mid-1
k-=1
elifkey>lis[mid]:
low=mid+1
k-=2
else:ifmid<=high:#打印查找的次數
print("times:%s"%time)returnmidelse:
print("times:%s"%time)returnhigh
print("times:%s"%time)returnFalseif__name__=='__main__':
LIST=[1,5,7,8,22,54,99,123,200,222,444]
result=fibonacci_search(LIST,444)
print(result)

算法分析：斐波那契查找的整體時間復雜度也為O(log(n))。但就平均性能，要優于二分查找。但是在最壞情況下，比如這里如果key為1，則始終處于左側半區查找，此時其效率要低于二分查找。

總結：二分查找的mid運算是加法與除法，插值查找則是復雜的四則運算，而斐波那契查找只是最簡單的加減運算。在海量數據的查找中，這種細微的差別可能會影響最終的查找效率。因此，三種有序表的查找方法本質上是分割點的選擇不同，各有優劣，應根據實際情況進行選擇。

四、線性索引查找

對于海量的無序數據，為了提高查找速度，一般會為其構造索引表。
索引就是把一個關鍵字與它相對應的記錄進行關聯的過程。
一個索引由若干個索引項構成，每個索引項至少包含關鍵字和其對應的記錄在存儲器中的位置等信息。
索引按照結構可以分為：線性索引、樹形索引和多級索引。
線性索引：將索引項的集合通過線性結構來組織，也叫索引表。
線性索引可分為：稠密索引、分塊索引和倒排索引

稠密索引

稠密索引指的是在線性索引中，為數據集合中的每個記錄都建立一個索引項。

這其實就相當于給無序的集合，建立了一張有序的線性表。其索引項一定是按照關鍵碼進行有序的排列。
這也相當于把查找過程中需要的排序工作給提前做了。

分塊索引

給大量的無序數據集合進行分塊處理，使得塊內無序，塊與塊之間有序。
這其實是有序查找和無序查找的一種中間狀態或者說妥協狀態。因為數據量過大，建立完整的稠密索引耗時耗力，占用資源過多；但如果不做任何排序或者索引，那么遍歷的查找也無法接受，只能折中，做一定程度的排序或索引。

分塊索引的效率比遍歷查找的O(n)要高一些，但與二分查找的O(logn)還是要差不少。

倒排索引

不是由記錄來確定屬性值，而是由屬性值來確定記錄的位置，這種被稱為倒排索引。其中記錄號表存儲具有相同次關鍵字的所有記錄的地址或引用（可以是指向記錄的指針或該記錄的主關鍵字）。

倒排索引是最基礎的搜索引擎索引技術。

總結

以上是生活随笔為你收集整理的Python中有哪些常用的查找数据结构及算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。