Python数据结构与算法(20)---插值查找

简介: Python数据结构与算法(20)---插值查找

插值查找


插值查找,又名Interpolation Search,是基于有序数列的元素查找,在采用二分查找算法的思想上进行了改进。


其在最小值与最大值范围内,用公式确定中间分割比较点mid。这里,我们具体的插值公式如下所示:


其时间复杂度为:O(loglogN)。


插值查找公式计算

假设,我们的数列还是[1,3,5,7,9,11,13],我们还是需要查找数值13。那么,根据上面的公式(left=0,right=6),我们计算得出mid=(13-1)*6/(13-1)=6,这样我们一次就能找到我们需要查找的元素13。


不过,需要注意的是,插值查找适用于元素分布比较均匀的情况,比如博主提供的数组,它们之间间隔仅为2,这就非常的均匀了。


如果不是分布均匀的数列,那么不适合插值查找算法。所以,我们在进行查找一个数据时,需要先分析数列的特点,然后选择合适的算法。


实战:插值查找

话不多说,我们直接通过Python实现查找插值,示例如下:

def Interpolation_search(my_list, key):
    left = 0
    right = len(my_list)-1
    while left <= right:
        mid = left + int((right - left) * (key - my_list[left]) / (my_list[right] - my_list[left]))
        if key < my_list[mid]:
            right = mid - 1
        elif key > my_list[mid]:
            left = mid + 1
        else:
            return mid
    return "None"
if __name__ == "__main__":
    my_list = [1, 3, 5, 7, 9, 11, 13]
    print("二分查找的原始数列:", my_list)
    print("二分查找的返回结果:", Interpolation_search(my_list, 13))


运行之后,效果如下:

相关文章
|
2月前
|
算法 前端开发 数据处理
小白学python-深入解析一位字符判定算法
小白学python-深入解析一位字符判定算法
48 0
|
2月前
|
机器学习/深度学习 算法 搜索推荐
从理论到实践,Python算法复杂度分析一站式教程,助你轻松驾驭大数据挑战!
【10月更文挑战第4天】在大数据时代,算法效率至关重要。本文从理论入手,介绍时间复杂度和空间复杂度两个核心概念,并通过冒泡排序和快速排序的Python实现详细分析其复杂度。冒泡排序的时间复杂度为O(n^2),空间复杂度为O(1);快速排序平均时间复杂度为O(n log n),空间复杂度为O(log n)。文章还介绍了算法选择、分而治之及空间换时间等优化策略,帮助你在大数据挑战中游刃有余。
63 4
|
2月前
|
机器学习/深度学习 缓存 算法
Python算法设计中的时间复杂度与空间复杂度,你真的理解对了吗?
【10月更文挑战第4天】在Python编程中,算法的设计与优化至关重要,尤其在数据处理、科学计算及机器学习领域。本文探讨了评估算法性能的核心指标——时间复杂度和空间复杂度。通过详细解释两者的概念,并提供快速排序和字符串反转的示例代码,帮助读者深入理解这些概念。同时,文章还讨论了如何在实际应用中平衡时间和空间复杂度,以实现最优性能。
69 6
|
5天前
|
存储 算法 搜索推荐
Python 中数据结构和算法的关系
数据结构是算法的载体,算法是对数据结构的操作和运用。它们共同构成了计算机程序的核心,对于提高程序的质量和性能具有至关重要的作用
|
18天前
|
机器学习/深度学习 Python
SciPy 教程 之 SciPy 插值 2
SciPy插值教程:介绍插值概念及其在数值分析中的应用,特别是在处理数据缺失时的插补和平滑数据集。SciPy的`scipy.interpolate`模块提供了强大的插值功能,如一维插值和样条插值。通过`UnivariateSpline()`函数,可以轻松实现单变量插值,示例代码展示了如何对非线性点进行插值计算。
22 3
|
16天前
|
机器学习/深度学习 人工智能 算法
基于Python深度学习的【垃圾识别系统】实现~TensorFlow+人工智能+算法网络
垃圾识别分类系统。本系统采用Python作为主要编程语言,通过收集了5种常见的垃圾数据集('塑料', '玻璃', '纸张', '纸板', '金属'),然后基于TensorFlow搭建卷积神经网络算法模型,通过对图像数据集进行多轮迭代训练,最后得到一个识别精度较高的模型文件。然后使用Django搭建Web网页端可视化操作界面,实现用户在网页端上传一张垃圾图片识别其名称。
63 0
基于Python深度学习的【垃圾识别系统】实现~TensorFlow+人工智能+算法网络
|
16天前
|
机器学习/深度学习 人工智能 算法
【手写数字识别】Python+深度学习+机器学习+人工智能+TensorFlow+算法模型
手写数字识别系统,使用Python作为主要开发语言,基于深度学习TensorFlow框架,搭建卷积神经网络算法。并通过对数据集进行训练,最后得到一个识别精度较高的模型。并基于Flask框架,开发网页端操作平台,实现用户上传一张图片识别其名称。
53 0
【手写数字识别】Python+深度学习+机器学习+人工智能+TensorFlow+算法模型
|
16天前
|
机器学习/深度学习 人工智能 算法
基于深度学习的【蔬菜识别】系统实现~Python+人工智能+TensorFlow+算法模型
蔬菜识别系统,本系统使用Python作为主要编程语言,通过收集了8种常见的蔬菜图像数据集('土豆', '大白菜', '大葱', '莲藕', '菠菜', '西红柿', '韭菜', '黄瓜'),然后基于TensorFlow搭建卷积神经网络算法模型,通过多轮迭代训练最后得到一个识别精度较高的模型文件。在使用Django开发web网页端操作界面,实现用户上传一张蔬菜图片识别其名称。
62 0
基于深度学习的【蔬菜识别】系统实现~Python+人工智能+TensorFlow+算法模型
|
21天前
|
算法 Python
在Python编程中,分治法、贪心算法和动态规划是三种重要的算法。分治法通过将大问题分解为小问题,递归解决后合并结果
在Python编程中,分治法、贪心算法和动态规划是三种重要的算法。分治法通过将大问题分解为小问题,递归解决后合并结果;贪心算法在每一步选择局部最优解,追求全局最优;动态规划通过保存子问题的解,避免重复计算,确保全局最优。这三种算法各具特色,适用于不同类型的问题,合理选择能显著提升编程效率。
37 2
|
2月前
|
存储 机器学习/深度学习 算法
蓝桥杯练习题(三):Python组之算法训练提高综合五十题
蓝桥杯Python编程练习题的集合,涵盖了从基础到提高的多个算法题目及其解答。
70 3
蓝桥杯练习题(三):Python组之算法训练提高综合五十题