Python实现线性搜索与插值搜索算法详解

Theo

发布时间：2026-10-13 | 5人浏览过

原创

本文详细介绍Python中两种基础搜索算法的实现。首先解析线性搜索原理及代码，适用于无序数据；其次深入讲解插值搜索，强调其对排序且均匀分布数据的依赖。通过完整Python代码示例，展示如何高效查找目标值，帮助开发者理解不同场景下的搜索策略选择。

搜索算法概述

当数据存储在各类数据结构中时，执行搜索操作是基础且必要的功能。最直观的搜索方式是对数据结构中的每个元素进行遍历，并将其与目标值进行比对，这种方法被称为线性搜索。尽管线性搜索效率较低且在实际生产中较少直接使用，但通过编写相关程序，可以为理解更高级的搜索算法提供基础思路。

线性搜索实现

线性搜索

线性搜索的核心机制是逐个检查数据集中的所有值。算法会依次验证每个元素，一旦发现与目标值匹配的元素，立即返回该元素的索引；若遍历至数据结构末尾仍未找到匹配项，则搜索结束。具体实现代码如下：

[Python] 纯文本查看


def linear_search(data, search_for):
 """线性搜索"""
 search_at = 0
 search_res = False
 while search_at < len(data) and search_res is False:
  if data[search_at] == search_for:
   search_res = True
  else:
   search_at += 1
 return search_res
lis = [5, 10, 7, 35, 12, 26, 41]
print(linear_search(lis, 12))
print(linear_search(lis, 6))

插值搜索原理与代码

插值搜索

插值搜索算法旨在预测目标值的探测位置，从而提高搜索效率。要使该算法正常工作，数据集必须保持排序状态且数据分布相对均匀。初始探测位置通常基于集合中最大项的位置进行计算。若发生匹配，则返回该项目的索引；若中间项目的值大于目标项目，算法将在中间项目右侧的子数组中重新计算探测位置；反之，则在左侧子数组中继续搜索。该过程在子数组上迭代执行，直到子数组大小缩减为零。具体实现代码如下：

[Python] 纯文本查看


def insert_search(data,x):
 """插值搜索"""
 idx0 = 0
 idxn = (len(data) - 1)
 while idx0 <= idxn and x >= data[idx0] and x <= data[idxn]:
  mid = idx0 +int(((float(idxn - idx0)/(data[idxn] - data[idx0])) * (x - data[idx0])))
  if data[mid] == x:
   return "在下标为"+str(mid) + "的位置找到了" + str(x)
  if data[mid] < x:
   idx0 = mid + 1
 return "没有搜索到" + str(x)
 
 
lis = [2, 6, 11, 19, 27, 31, 45, 121]
print(insert_search(lis, 31))
print(insert_search(lis, 3))

总结

以上内容介绍了使用Python实现线性搜索与插值搜索的实例代码，希望能为读者提供帮助。如有任何疑问，欢迎留言，小编将及时回复。感谢大家对本站的支持！如果您觉得本文对您有帮助，欢迎转载，请注明出处，谢谢！