Python数据结构与算法(19)---二分查找

简介: Python数据结构与算法(19)---二分查找

二分查找


二分查找又名Binary Search,其采用折半的查找方式,实现对有序元素的快速查找。


相信看到上面二分查找的定义,读者很容易就能想到,二分查找有一个非常重要的前提条件,那就是其需要已经排序好的数列。这样,我们折半查找可以缩小查找的次数,更加的高效。


其具体原理:在数列中取中间下标值mid的元素e,进行查找元素key的比较。如果相等即查找成功,如果不等,大于就只需要在后半部分查找,小于需要在前半部分查找。


不管是前半部分还是后半部分,我们在取其中间值mid,进行比较,依次类推,直到mid值等于key结束查找。


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


图解二分查找

假设,我们现在有一个数列[1,3,5,7,9,11,13],我们需要查找13所在的索引位置,那么的步骤应该分几步?


如上图所示,我们这里先取中间索引值3,与13进行比较。13不等于list[3],且大于它,接下来我们需要取后半部分进行查找。


同样的,在取后半部分中间值进行比较,依然大于它。最后,我们只剩下一个值,如果相等,返回查找到的索引,如果不等,返回查询不到。


实战:二分查找

了解其具体的原理之后,我们接下来通过Python来实现其二分查找的具体效果。示例代码如下所示:

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


运行之后,效果如下:


相关文章
|
4天前
|
算法 开发者 计算机视觉
燃爆全场!Python并查集:数据结构界的网红,让你的代码炫酷无比!
在编程的世界里,总有一些数据结构以其独特的魅力和高效的性能脱颖而出,成为众多开发者追捧的“网红”。今天,我们要介绍的这位明星,就是Python中的并查集(Union-Find)——它不仅在解决特定问题上大放异彩,更以其优雅的设计和强大的功能,让你的代码炫酷无比,燃爆全场!
17 0
|
2天前
|
算法 安全 Go
RSA加密算法详解与Python和Go实现
RSA加密算法详解与Python和Go实现
8 1
|
2天前
|
存储 算法 安全
Python 加密算法详解与应用
Python 加密算法详解与应用
9 1
|
5天前
|
存储 算法 Python
火箭般的提升!学会Python并查集,让你的算法能力飞跃新高度!
火箭般的提升!学会Python并查集,让你的算法能力飞跃新高度!
15 1
|
14天前
|
存储 索引 Python
Python常用数据结构——集合
Python常用数据结构——集合
34 3
|
14天前
|
存储 数据安全/隐私保护 Python
Python常用数据结构——字典的应用
Python常用数据结构——字典的应用
15 2
|
16天前
|
Python
逆天改命!掌握Python并查集,数据结构难题从此不再是你的痛!
在编程旅程中,遇到棘手的数据结构难题是否让你苦恼?别担心,Python并查集(Union-Find)是你的得力助手。这是一种高效处理不相交集合合并及查询的数据结构,广泛应用于网络连通性、社交网络圈子划分等场景。通过维护每个集合的根节点,它实现了快速合并与查询。本文将介绍并查集的基本概念、应用场景以及如何在Python中轻松实现并查集,帮助你轻松应对各种数据结构挑战。
27 3
|
2天前
|
算法 安全 Go
Python与Go语言中的哈希算法实现及对比分析
Python与Go语言中的哈希算法实现及对比分析
12 0
|
2天前
|
安全 测试技术 Go
Python 和 Go 实现 AES 加密算法的技术详解
Python 和 Go 实现 AES 加密算法的技术详解
8 0
|
3天前
|
算法 Python
逆袭之路!用 Python 玩转图的 DFS 与 BFS,让数据结构难题无处遁形
在数据结构的广袤领域中,图是一种强大而复杂的结构,而深度优先搜索(DFS)和广度优先搜索(BFS)则是遍历图的两把利剑。Python 以其简洁和强大的特性,为我们提供了实现和运用这两种算法的便捷途径。
18 0