Python - 搜尋演算法

當您將資料儲存在不同的資料結構中時，搜尋是一個非常基本的需求。最簡單的方法是遍歷資料結構中的每個元素，並將其與您要搜尋的值進行匹配。這被稱為線性搜尋。它效率低下，很少使用，但是為其建立程式可以讓我們瞭解如何實現一些高階搜尋演算法。

線性搜尋

在這種型別的搜尋中，會對所有專案逐個進行順序搜尋。檢查每個專案，如果找到匹配項，則返回該特定專案，否則搜尋將繼續到資料結構的末尾。

示例

def linear_search(values, search_for):
   search_at = 0
   search_res = False
# Match the value with each data element	
   while search_at < len(values) and search_res is False:
      if values[search_at] == search_for:
         search_res = True
      else:
         search_at = search_at + 1
   return search_res
l = [64, 34, 25, 12, 22, 11, 90]
print(linear_search(l, 12))
print(linear_search(l, 91))

輸出

執行上述程式碼後，將產生以下結果：

True
False

插值搜尋

此搜尋演算法基於所需值的探測位置。為了使此演算法正常工作，資料集合應已排序且均勻分佈。最初，探測位置是集合中最中間專案的索引位置。如果找到匹配項，則返回該專案的索引。如果中間項大於該項，則在中間項右側的子陣列中再次計算探測位置。否則，在中間項左側的子陣列中搜索該項。此過程也在子陣列上繼續進行，直到子陣列的大小減小到零。

示例

下面程式中指出了計算中間位置的特定公式：

def intpolsearch(values,x ):
   idx0 = 0
   idxn = (len(values) - 1)
   while idx0 <= idxn and x >= values[idx0] and x <= values[idxn]:
# Find the mid point
	mid = idx0 +\
      int(((float(idxn - idx0)/( values[idxn] - values[idx0]))
      * ( x - values[idx0])))
# Compare the value at mid point with search value 
   if values[mid] == x:
      return "Found "+str(x)+" at index "+str(mid)
   if values[mid] < x:
      idx0 = mid + 1
   return "Searched element not in the list"

l = [2, 6, 11, 19, 27, 31, 45, 121]
print(intpolsearch(l, 2))

輸出

執行上述程式碼後，將產生以下結果：

Found 2 at index 0