二分查找算法学习札记
说明
作者:那谁
blog: http://www.cppblog.com/converse
转载请注明出处.
二分查找算法基本思想
二分查找算法的前置条件是,一个已经排序好的序列(在本篇文章中为了说明问题的方便,假设这个序列是升序排列的),这样在查找所要查找的元素时,首先与序列中间的元素进行比较,如果大于这个元素,就在当前序列的后半部分继续查找,如果小于这个元素,就在当前序列的前半部分继续查找,直到找到相同的元素,或者所查找的序列范围为空为止.
用伪代码来表示, 二分查找算法大致是这个样子的:
while (left <= right)
mid = (left + right) / 2
case
x[mid] < t: left = mid + 1;
x[mid] = t: p = mid; break;
x[mid] > t: right = mid -1;
return -1;
下面,讲讲在编写二分查找算法时可能出现的一些问题.
边界错误造成的问题
二分查找算法的边界,一般来说分两种情况,一种是左闭右开区间,类似于[left, right),一种是左闭右闭区间,类似于[left, right].需要注意的是, 循环体外的初始化条件,与循环体内的迭代步骤, 都必须遵守一致的区间规则,也就是说,如果循环体初始化时,是以左闭右开区间为边界的,那么循环体内部的迭代也应该如此.如果两者不一致,会造成程序的错误.比如下面就是错误的二分查找算法:
{
int left, right, middle;
left = 0, right = n;
while (left < right)
{
middle = (left + right) / 2;
if (array[middle] > v)
{
right = middle - 1;
}
else if (array[middle] < v)
{
left = middle + 1;
}
else
{
return middle;
}
}
return -1;
}
这个算法的错误在于, 在循环初始化的时候,初始化right=n,也就是采用的是左闭右开区间,而当满足array[middle] > v的条件是, v如果存在的话应该在[left, middle)区间中,但是这里却把right赋值为middle - 1了,这样,如果恰巧middle-1就是查找的元素,那么就会找不到这个元素.
下面给出两个算法, 分别是正确的左闭右闭和左闭右开区间算法,可以与上面的进行比较:
{
int left, right, middle;
left = 0, right = n - 1;
while (left <= right)
{
middle = (left + right) / 2;
if (array[middle] > v)
{
right = middle - 1;
}
else if (array[middle] < v)
{
left = middle + 1;
}
else
{
return middle;
}
}
return -1;
}
int search3(int array[], int n, int v)
{
int left, right, middle;
left = 0, right = n;
while (left < right)
{
middle = (left + right) / 2;
if (array[middle] > v)
{
right = middle;
}
else if (array[middle] < v)
{
left = middle + 1;
}
else
{
return middle;
}
}
return -1;
}
死循环
上面的情况还只是把边界的其中一个写错, 也就是右边的边界值写错, 如果两者同时都写错的话,可能会造成死循环,比如下面的这个程序:
{
int left, right, middle;
left = 0, right = n - 1;
while (left <= right)
{
middle = (left + right) / 2;
if (array[middle] > v)
{
right = middle;
}
else if (array[middle] < v)
{
left = middle;
}
else
{
return middle;
}
}
return -1;
}
这个程序采用的是左闭右闭的区间.但是,当array[middle] > v的时候,那么下一次查找的区间应该为[middle + 1, right], 而这里变成了[middle, right];当array[middle] < v的时候,那么下一次查找的区间应该为[left, middle - 1], 而这里变成了[left, middle].两个边界的选择都出现了问题, 因此,有可能出现某次查找时始终在这两个范围中轮换,造成了程序的死循环.
溢出
前面解决了边界选择时可能出现的问题, 下面来解决另一个问题,其实这个问题严格的说不属于算法问题,不过我注意到很多地方都没有提到,我觉得还是提一下比较好.
在循环体内,计算中间位置的时候,使用的是这个表达式:
假如,left与right之和超过了所在类型的表示范围的话,那么middle就不会得到正确的值.
所以,更稳妥的做法应该是这样的:
更完善的算法
前面我们说了,给出的第一个算法是一个"正确"的程序, 但是还有一些小的问题.
首先, 如果序列中有多个相同的元素时,查找的时候不见得每次都会返回第一个元素的位置, 比如考虑一种极端情况:序列中都只有一个相同的元素,那么去查找这个元素时,显然返回的是中间元素的位置.
其次, 前面给出的算法中,每次循环体中都有三次情况,两次比较,有没有办法减少比较的数量进一步的优化程序?
<<编程珠玑>>中给出了解决这两个问题的算法,结合前面提到溢出问题我对middle的计算也做了修改:
{
int left, right, middle;
left = -1, right = n;
while (left + 1 != right)
{
middle = left + (right - left) / 2;
if (array[middle] < v)
{
left = middle;
}
else
{
right = middle;
}
}
if (right >= n || array[right] != v)
{
right = -1;
}
return right;
}
这个算法是所有这里给出的算法中最完善的一个,正确,精确且效率高.
参考资料
1.<<编程珠玑>>
2.wiki上关于二分查找的说明:http://en.wikipedia.org/wiki/Binary_search
相关推荐
“二分查找学习札记.pdf”很可能包含了关于二分查找的深入分析、实例演示以及相关的编程练习,可以帮助初学者更好地理解并掌握这一算法。通过系统学习和实践,你可以逐步克服对二分查找的恐惧,提高自己的算法能力。
2. 自动整理:利用AI算法,自动分类和标记笔记,便于查找。 3. 智能搜索:通过关键词或主题搜索,快速定位所需笔记。 4. 同步备份:云同步功能确保用户数据安全,可在多设备间无缝切换。 5. 分享互动:用户可以分享...
3. **算法**:排序(如冒泡、选择、插入、快速排序等)、查找(线性、二分查找等)和图算法(如深度优先搜索、广度优先搜索)是基础。通过学习和分析复杂度,可以优化代码性能。 4. **面向对象编程**:类与对象的...
资源内项目源码是来自个人的毕业设计,代码都测试ok,包含源码、数据集、可视化页面和部署说明,可产生核心指标曲线图、混淆矩阵、F1分数曲线、精确率-召回率曲线、验证集预测结果、标签分布图。都是运行成功后才上传资源,毕设答辩评审绝对信服的保底85分以上,放心下载使用,拿来就能用。包含源码、数据集、可视化页面和部署说明一站式服务,拿来就能用的绝对好资源!!! 项目备注 1、该资源内项目代码都经过测试运行成功,功能ok的情况下才上传的,请放心下载使用! 2、本项目适合计算机相关专业(如计科、人工智能、通信工程、自动化、电子信息等)的在校学生、老师或者企业员工下载学习,也适合小白学习进阶,当然也可作为毕设项目、课程设计、大作业、项目初期立项演示等。 3、如果基础还行,也可在此代码基础上进行修改,以实现其他功能,也可用于毕设、课设、作业等。 下载后请首先打开README.txt文件,仅供学习参考, 切勿用于商业用途。
《基于YOLOv8的智慧社区独居老人生命体征监测系统》(包含源码、可视化界面、完整数据集、部署教程)简单部署即可运行。功能完善、操作简单,适合毕设或课程设计
Android Studio Meerkat 2024.3.1 Patch 1(android-studio-2024.3.1.14-mac.dmg)适用于macOS Intel系统,文件使用360压缩软件分割成两个压缩包,必须一起下载使用: part1: https://download.csdn.net/download/weixin_43800734/90557060 part2: https://download.csdn.net/download/weixin_43800734/90557056
侧轴承杯加工工艺编制及夹具设计.zip
NASA数据集锂电池容量特征提取(Matlab完整源码和数据) 作者介绍:机器学习之心,博客专家认证,机器学习领域创作者,2023博客之星TOP50,主做机器学习和深度学习时序、回归、分类、聚类和降维等程序设计和案例分析,文章底部有博主联系方式。从事Matlab、Python算法仿真工作8年,更多仿真源码、数据集定制私信。
板料折弯机液压系统设计.zip
C6150车床的设计.zip
机器学习之KNN实现手写数字
python爬虫;智能切换策略,反爬检测机制
mpls-vpn-optionA-all
56tgyhujikolp[
GB 6442-86企业职工伤亡事故调查分析规则.pdf
汽车液压式主动悬架系统的设计().zip
2000-2024年各省专利侵权案件结案数数据 1、时间:2000-2024年 2、来源:国家知识产权J 3、指标:专利侵权案件结案数 4、范围:31省 5、用途:可用于衡量知识产权保护水平
资源内项目源码是来自个人的毕业设计,代码都测试ok,包含源码、数据集、可视化页面和部署说明,可产生核心指标曲线图、混淆矩阵、F1分数曲线、精确率-召回率曲线、验证集预测结果、标签分布图。都是运行成功后才上传资源,毕设答辩评审绝对信服的保底85分以上,放心下载使用,拿来就能用。包含源码、数据集、可视化页面和部署说明一站式服务,拿来就能用的绝对好资源!!! 项目备注 1、该资源内项目代码都经过测试运行成功,功能ok的情况下才上传的,请放心下载使用! 2、本项目适合计算机相关专业(如计科、人工智能、通信工程、自动化、电子信息等)的在校学生、老师或者企业员工下载学习,也适合小白学习进阶,当然也可作为毕设项目、课程设计、大作业、项目初期立项演示等。 3、如果基础还行,也可在此代码基础上进行修改,以实现其他功能,也可用于毕设、课设、作业等。 下载后请首先打开README.txt文件,仅供学习参考, 切勿用于商业用途。
内容概要:本文档详细复现了金融数学课程作业,涵盖欧式看涨期权定价和投资组合优化两大部分。对于欧式看涨期权定价,分别采用Black-Scholes模型和蒙特卡洛方法进行了计算,并对彩虹期权进行了基于最大值的看涨期权定价。投资组合优化部分则探讨了最小方差组合、给定收益的最小方差组合、最大效用组合以及给定风险的最大收益组合四种情形,还对比了拉格朗日乘数法和二次规划求解器两种方法。文中不仅提供了详细的MATLAB代码,还有详尽的中文解释,确保每一步骤清晰明了。 适合人群:金融工程专业学生、量化分析师、金融数学爱好者。 使用场景及目标:①帮助学生理解和掌握金融衍生品定价的基本原理和方法;②为从事量化分析的专业人士提供实用工具和技术支持;③作为教学材料辅助高校教师讲授相关内容。 其他说明:文档还包括了完整的论文结构建议,从封面页到结论,再到附录,涵盖了所有必要元素,确保提交的作业符合学术规范。此外,还特别强调了数据预处理步骤,确保代码可以顺利运行。
脉冲电解射流加工喷射装置设计(1)