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))


运行之后,效果如下:


相关文章
|
13天前
|
算法 数据安全/隐私保护 开发者
马特赛特旋转算法:Python的随机模块背后的力量
马特赛特旋转算法是Python `random`模块的核心,由松本真和西村拓士于1997年提出。它基于线性反馈移位寄存器,具有超长周期和高维均匀性,适用于模拟、密码学等领域。Python中通过设置种子值初始化状态数组,经状态更新和输出提取生成随机数,代码简单高效。
101 63
|
6天前
|
机器学习/深度学习 人工智能 算法
【宠物识别系统】Python+卷积神经网络算法+深度学习+人工智能+TensorFlow+图像识别
宠物识别系统,本系统使用Python作为主要开发语言,基于TensorFlow搭建卷积神经网络算法,并收集了37种常见的猫狗宠物种类数据集【'阿比西尼亚猫(Abyssinian)', '孟加拉猫(Bengal)', '暹罗猫(Birman)', '孟买猫(Bombay)', '英国短毛猫(British Shorthair)', '埃及猫(Egyptian Mau)', '缅因猫(Maine Coon)', '波斯猫(Persian)', '布偶猫(Ragdoll)', '俄罗斯蓝猫(Russian Blue)', '暹罗猫(Siamese)', '斯芬克斯猫(Sphynx)', '美国斗牛犬
57 29
【宠物识别系统】Python+卷积神经网络算法+深度学习+人工智能+TensorFlow+图像识别
|
12天前
|
存储 算法 搜索推荐
Python 中数据结构和算法的关系
数据结构是算法的载体,算法是对数据结构的操作和运用。它们共同构成了计算机程序的核心,对于提高程序的质量和性能具有至关重要的作用
|
27天前
|
Python
二分查找变种大赏!Python 中那些让你效率翻倍的搜索绝技!
二分查找是一种高效的搜索算法,适用于有序数组。其基本原理是通过不断比较中间元素来缩小搜索范围,从而快速找到目标值。常见的变种包括查找第一个等于目标值的元素、最后一个等于目标值的元素、第一个大于等于目标值的元素等。这些变种在实际应用中能够显著提高搜索效率,适用于各种复杂场景。
36 9
|
28天前
|
算法 数据处理 开发者
超越传统:Python二分查找的变种策略,让搜索效率再上新台阶!
本文介绍了二分查找及其几种Python实现的变种策略,包括经典二分查找、查找第一个等于给定值的元素、查找最后一个等于给定值的元素以及旋转有序数组的搜索。通过调整搜索条件和边界处理,这些变种策略能够适应更复杂的搜索场景,提升搜索效率和应用灵活性。
32 5
|
24天前
|
机器学习/深度学习 人工智能 算法
基于Python深度学习的【垃圾识别系统】实现~TensorFlow+人工智能+算法网络
垃圾识别分类系统。本系统采用Python作为主要编程语言,通过收集了5种常见的垃圾数据集('塑料', '玻璃', '纸张', '纸板', '金属'),然后基于TensorFlow搭建卷积神经网络算法模型,通过对图像数据集进行多轮迭代训练,最后得到一个识别精度较高的模型文件。然后使用Django搭建Web网页端可视化操作界面,实现用户在网页端上传一张垃圾图片识别其名称。
71 0
基于Python深度学习的【垃圾识别系统】实现~TensorFlow+人工智能+算法网络
|
24天前
|
机器学习/深度学习 人工智能 算法
【手写数字识别】Python+深度学习+机器学习+人工智能+TensorFlow+算法模型
手写数字识别系统,使用Python作为主要开发语言,基于深度学习TensorFlow框架,搭建卷积神经网络算法。并通过对数据集进行训练,最后得到一个识别精度较高的模型。并基于Flask框架,开发网页端操作平台,实现用户上传一张图片识别其名称。
67 0
【手写数字识别】Python+深度学习+机器学习+人工智能+TensorFlow+算法模型
|
24天前
|
机器学习/深度学习 人工智能 算法
基于深度学习的【蔬菜识别】系统实现~Python+人工智能+TensorFlow+算法模型
蔬菜识别系统,本系统使用Python作为主要编程语言,通过收集了8种常见的蔬菜图像数据集('土豆', '大白菜', '大葱', '莲藕', '菠菜', '西红柿', '韭菜', '黄瓜'),然后基于TensorFlow搭建卷积神经网络算法模型,通过多轮迭代训练最后得到一个识别精度较高的模型文件。在使用Django开发web网页端操作界面,实现用户上传一张蔬菜图片识别其名称。
67 0
基于深度学习的【蔬菜识别】系统实现~Python+人工智能+TensorFlow+算法模型
|
28天前
|
算法 Python
在Python编程中,分治法、贪心算法和动态规划是三种重要的算法。分治法通过将大问题分解为小问题,递归解决后合并结果
在Python编程中,分治法、贪心算法和动态规划是三种重要的算法。分治法通过将大问题分解为小问题,递归解决后合并结果;贪心算法在每一步选择局部最优解,追求全局最优;动态规划通过保存子问题的解,避免重复计算,确保全局最优。这三种算法各具特色,适用于不同类型的问题,合理选择能显著提升编程效率。
40 2
|
1月前
|
算法 测试技术 开发者
在Python开发中,性能优化和代码审查至关重要。性能优化通过改进代码结构和算法提高程序运行速度,减少资源消耗
在Python开发中,性能优化和代码审查至关重要。性能优化通过改进代码结构和算法提高程序运行速度,减少资源消耗;代码审查通过检查源代码发现潜在问题,提高代码质量和团队协作效率。本文介绍了一些实用的技巧和工具,帮助开发者提升开发效率。
40 3