上一节:
下一节:

  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
上一节:
下一节: