c++与python实现二分查找的原理及实现
作者:机器学习入坑者 发布时间:2021-11-23 21:09:06
在计算机中,数据的查找方式与其存储方式关系密切。试想一下,如果图书馆中书籍杂乱无章的存放,那么要想找到心仪的书籍将会非常困难。为此,人们常常将物品按照某种规则或次序进行放置,目的是便于日后的查找。
作为查找算法家族中的一员,二分查找正是利用数据按次序存储这一优点,极大的提升了查找目标值所在位置的速度。
二分查找的核心思想是:首先将数组中间值和目标值进行比较,如果相等则返回;如果不相等,则选择中间值左边的一半或者右边的一半进行比较;不断重复直到检索完毕。首先来看下面这个gif,其中蓝色圈表示左位置,粉色圈表示右位置,绿色圈表示中间位置:
首先定义的是左边界(蓝色圈)和右边界(粉色圈),进而根据左边界和右边界计算出中间位置(绿色圈);然后,比较中间位置的值和目标值的大小,比较结果包含3种情况
如果相等则表示查找成功,返回中间位置;
如果中间位置的值小于目标值,则说明目标值在中间位置到右边界这一半;
如果中间位置的值大于目标值,则说明目标值在左边界到中间位置这一半;
上述步骤的循环需要终止条件,即左边界小于或等于右边界,表明此时已经搜索完成,目标数值不在数据中存在。
1、时间复杂度与优缺点
既然每次搜索后区间长度都减半,假设数据个数(即区间长度)为n,那么算法每次迭代得到的区间长度依次为n/2,n/4,n/8等等,其通项如下,k表示循环次数:
最坏的情况,就是搜索到区间长度为1,即最后只剩1个元素:
所以,可以求得最坏情况下需要运行的次数为:
因此二分查找复杂度为O(logn),相比于顺序查找其速度获得了极大的提高(优点)。但是,必须注意二分查找需要保证数据是有序的,这就要求数据必须预先进行排序(缺点)。
2、python实现
def binary_search(ordered_list, target_value):
? ? """
? ? Args:
? ? ? ? ordered_list: data with order
? ? ? ? target_value: value that want be searched
? ? """
? ? left = 0
? ? right = len(ordered_list)-1
? ? # 终止条件
? ? while left <= right:
? ? ? ? # 中间位置计算
? ? ? ? mid = int((left+right)/2)
? ? ? ? if ordered_list[mid] == target_value:
? ? ? ? ? ? return "index is {}, target value is {}".format(mid, ordered_list[mid])
? ? ? ? # 此时目标值在中间值右边,更新左位置
? ? ? ? elif ordered_list[mid] < target_value:
? ? ? ? ? ? left = mid + 1
? ? ? ? # 此时目标值在中间值左边,更新右位置
? ? ? ? elif ordered_list[mid] > target_value:
? ? ? ? ? ? right = mid - 1
? ? # 搜索结束没有找到
? ? return "Not find"
3、C++实现
int binarySearch(int *orderedData, int dataLength, int targetValue) {
?? ?int left = 0;
?? ?int right = dataLength - 1;
?? ?int mid;
?? ?// 终止条件
?? ?while (left<=right)
?? ?{
?? ??? ?// 中间位置计算
?? ??? ?mid = (left + right) / 2;
?? ??? ?if (*(orderedData + mid) == targetValue) {
?? ??? ??? ?return mid;
?? ??? ?}
?? ??? ?// 目标值在中间值右边,更新左位置
?? ??? ?else if (*(orderedData + mid) < targetValue){
?? ??? ??? ?left = mid + 1;
?? ??? ?}
?? ??? ?// 目标值在中间值左边,更新右位置
?? ??? ?else
?? ??? ?{
?? ??? ??? ?right = mid - 1;
?? ??? ?}
?? ?}
?? ?// 搜索不到,返回-1
?? ?return -1;
}
来源:https://zhuanlan.zhihu.com/p/105906443
猜你喜欢
- 前言我们有时候会编写Python脚本来辅助我们执行一些重复的操作。但是这些脚本在实际使用中会有一些不方便:我们通常需要进入终端或者IDE中来
- 自学Django已经有一周啦,想把自己自学过程中的每一步都记录下来,给一些零基自学Django的战友们一些参考;本次主要内容为,用一个实例展
- 最近想做实时目标检测,需要用到python开启摄像头,我手上只有两个uvc免驱的摄像头,性能一般。利用python开启摄像头费了一番功夫,主
- 如下所示:def save(data, path): f = xlwt.Workbook() # 创建工作簿 she
- 1、Model signalsdjango.db.models.signales 作用于django的model操作上的一系列信号1)pre
- 环境系统:win10cpu:i7-6700HQgpu:gtx965mpython : 3.6pytorch :0.3数据下载来源自Sasan
- 1. ASCII 返回与指定的字符对应的十进制数; SQL> select ascii(A) A,ascii(a) a,ascii(0
- 在使用matplotlib绘制图片时,x轴的刻度可能比较密集,特别是以日期作为x轴时,则最后会显示不出来。数据如下,速度V的数组与时间字符串
- 本文实例讲述了python实现根据月份和日期得到星座的方法。分享给大家供大家参考。具体实现方法如下:#计算星座def Zodiac(mont
- 本文介绍使用ADODB.Stream组件来下载服务器文件,例如:download.asp?file=相对路径的文件。就可以把这个文件下载下来
- 根据我最近的一些实践以及在和一些读者进行关于HTML表格的使用问题沟通之后,决定写这篇文章。总的来说,我注意到由于误导性信息,他们对于tab
- 本文研究的主要内容是Python中装饰器相关学习总结,具体如下。装饰器(decorator)功能引入日志函数执行时间统计执行函数前预备处理执
- 在oracle中有很多关于日期的函数,如:1、add_months()用于从一个日期值增加或减少一些月份date_value:=add_mo
- SQL Server 2000安装问题集锦1、先把SQL Server卸载(卸载不掉也没有关系,继续下面的操作)2、把Microsoft S
- 环境ubuntu 12.04 LTSpython 2.7.3opencv 2.3.1-7安装依赖sudo apt-get install l
- 取反运算符的原理:1.对3取反:(取4位二进制)①化为二进制:3→0011②对二进制结果取反:0011→1100③对结果先取反再加1:110
- 本文实例讲述了python 函数的缺省参数使用注意事项。分享给大家供大家参考,具体如下:python的函数支持4种形式的参数:分别是必选参数
- 单线程实现多个定时器NewTimer.py#!/usr/bin/env pythonfrom heapq import *from thre
- pandas的qcut可以把一组数字按大小区间进行分区,比如data = pd.Series([0,8,1,5,3,7,2,6,10,4,9
- 目录各种姿势比较快的姿势最后各种姿势比如说有一个简单的任务,就是从 1 累加到 1 亿,我们至少可以有 7 种方法来实现,列举如下:1、wh