本篇文章给大家带来了关于python的相关知识,其中主要整理了二分查找算法的相关问题,包括了算法描述、算法分析、算法思路等等内容,下面一起来看一下,希望对大家有帮助。
推荐学习:python视频教程
二分法是一种效率比较高的搜索方法
回忆之前做过的猜数字的小游戏,预先给定一个小于100的正整数x,让你猜猜测过程中给予大小判断的提示,问你怎样快速地猜出来?
我们之前做的游戏给定的是10次机会,如果我们学会.二分查找法以后,不管数字是多少,最多只需要7次就能猜到数字。
1、必须是有序的序列。
2、对数据量大小有要求。
数据量太小不适合二分查找,与直接遍历相比效率提升不明显。
数据量太大也不适合用二分查找,因为数组需要连续的存储空间,若数据量太大,往往找不到存储如此大规模数据的连续内存空间。.
假设有一个有序列表如下:
请问数字11是否在此列表中,如果在它的索引值为多少?
实现代码:
arr_list = [5, 7, 11, 22, 27, 33, 39, 52, 58]# 需要查找的数字seek_number = 11# 保存一共查找了几次count = 0# 列表左侧索引left = 0# 列表右侧索引right = len(arr_list) - 1# 当左侧索引小于等于右侧索引时while left arr_list[middle]: # 左侧索引为中间位置索引+1 left = middle + 1 # 如果查找的数字小于中间位置的数字时 elif seek_number <p>运行结果:</p><p><img src="https://img.php.cn/upload/article/000/000/067/ab7ca007166584d2196443b3030f239a-4.png" alt="在这里插入图片描述"></p><h2>递归法实现</h2><blockquote><p>在循环中定义了一个变量count,如果第一次循环后count没有变化,就说明输入的是有序序列,这时我们直接return退出循环,这时候的时间复杂度为O(n)</p></blockquote><p>实现代码:</p><pre class="brush:php;toolbar:false">arr_list = [5, 7, 11, 22, 27, 33, 39, 52, 58]def binary_search(seek_number, left, right): if left arr_list[middle]: left = middle + 1 else: return middle # 进行递归调用 return binary_search(seek_number, left, right) # 当左侧索引大于右侧索引时,说明没有找到 else: return -1# 查找的数字seek_number = 11# 列表左侧索引left = 0# 列表右侧索引right = len(arr_list) - 1print("查找的数字:%s,索引为:%s" % (seek_number, binary_search(seek_number, left, right)))
运行结果:
推荐学习:python视频教程
以上就是Python详细解析之二分查找算法的详细内容,更多请关注php中文网其它相关文章!
Copyright 2014-2024 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号