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中的并查集(Union-Find)——它不仅在解决特定问题上大放异彩,更以其优雅的设计和强大的功能,让你的代码炫酷无比,燃爆全场!
9 0
|
23小时前
|
存储 算法 安全
Python 加密算法详解与应用
Python 加密算法详解与应用
6 1
|
3天前
|
存储 算法 Python
火箭般的提升!学会Python并查集,让你的算法能力飞跃新高度!
火箭般的提升!学会Python并查集,让你的算法能力飞跃新高度!
12 1
|
13天前
|
存储 索引 Python
Python常用数据结构——集合
Python常用数据结构——集合
32 3
|
13天前
|
存储 数据安全/隐私保护 Python
Python常用数据结构——字典的应用
Python常用数据结构——字典的应用
14 2
|
15天前
|
Python
逆天改命!掌握Python并查集,数据结构难题从此不再是你的痛!
在编程旅程中,遇到棘手的数据结构难题是否让你苦恼?别担心,Python并查集(Union-Find)是你的得力助手。这是一种高效处理不相交集合合并及查询的数据结构,广泛应用于网络连通性、社交网络圈子划分等场景。通过维护每个集合的根节点,它实现了快速合并与查询。本文将介绍并查集的基本概念、应用场景以及如何在Python中轻松实现并查集,帮助你轻松应对各种数据结构挑战。
26 3
|
15天前
|
大数据 UED 开发者
实战演练:利用Python的Trie树优化搜索算法,性能飙升不是梦!
在数据密集型应用中,高效搜索算法至关重要。Trie树(前缀树/字典树)通过优化字符串处理和搜索效率成为理想选择。本文通过Python实战演示Trie树构建与应用,显著提升搜索性能。Trie树利用公共前缀减少查询时间,支持快速插入、删除和搜索。以下为简单示例代码,展示如何构建及使用Trie树进行搜索与前缀匹配,适用于自动补全、拼写检查等场景,助力提升应用性能与用户体验。
35 2
|
23小时前
|
算法 安全 Go
Python与Go语言中的哈希算法实现及对比分析
Python与Go语言中的哈希算法实现及对比分析
8 0
|
23小时前
|
安全 测试技术 Go
Python 和 Go 实现 AES 加密算法的技术详解
Python 和 Go 实现 AES 加密算法的技术详解
6 0
|
1天前
|
算法 Python
逆袭之路!用 Python 玩转图的 DFS 与 BFS,让数据结构难题无处遁形
在数据结构的广袤领域中,图是一种强大而复杂的结构,而深度优先搜索(DFS)和广度优先搜索(BFS)则是遍历图的两把利剑。Python 以其简洁和强大的特性,为我们提供了实现和运用这两种算法的便捷途径。
13 0