在线客服
扫描二维码
下载博学谷APP
扫描二维码
关注博学谷微信公众号
二分法检索变种实现代码怎么写？二分法中每次排除都可以排除掉一半的情况，这样寻找效率很高。之所以叫二分，因为每次排除都把所有的情况分成"可能"和"不可能"两种,然后抛弃所有"不可能"的情况。
二分法真的不简单，尤其是二分法的各个变种。最简单的二分法，就是从一个排好序的数组之查找一个key值。如下面的程序：
这个程序，相信只要是一个合格的程序员应该都会写。稍微注意一点， 每次移动left和right指针的时候，需要在mid的基础上+1或者-1， 防止出现死循环， 程序也就能够正确的运行。
但如果条件稍微变化一下， 你还会写吗？如，数组之中的数据可能可以重复，要求返回匹配的数据的最小（或最大）的下标；更近一步， 需要找出数组中第一个大于key的元素（也就是最小的大于key的元素的）下标，等等。这些，虽然只有一点点的变化，实现的时候确实要更加的细心。下面列出了这些二分检索变种的实现。
1、找出第一个与key相等的元素
2、找出最后一个与key相等的元素
3、查找第一个等于或者大于Key的元素
4、查找第一个大于key的元素
5、查找最后一个等于或者小于key的元素
6、查找最后一个小于key的元素
总结：
算法：当数据量很大适宜采用该方法。采用二分法查找时，数据需是排好序的。
基本思想：假设数据是按升序排序的，对于给定值key，从序列的中间位置k开始比较，
如果当前位置arr[k]值等于key，则查找成功；
若key小于当前位置值arr[k]，则在数列的前半段中查找,arr[low,mid-1]；
若key大于当前位置值arr[k]，则在数列的后半段中继续查找arr[mid+1,high]，
直到找到为止,时间复杂度:O(log(n))。
— 申请免费试学名额 —
在职想转行提升，担心学不会？根据个人情况规划学习路线，闯关式自适应学习模式保证学习效果
讲师一对一辅导，在线答疑解惑，指导就业！
上一篇：
博学谷学员参加新网银行金融科技挑战赛获优胜奖
下一篇：
程序员常用的API接口管理工具有哪些？
相关推荐 更多
详解JDBC的运行过程
本文将从JDBC的作用，JDBC的连接步骤和JDBC的最佳实践三个方面来详解JDBC的运行过程，感兴趣的同学可以接着往下看，相信你一定会有所收获。
8299
2019-07-25 20:10:54
2019年11月IT编程语言排行榜 年底C语言将逆袭Java？
2019年11月IT编程语言排行榜年底C语言将逆袭Java？，热门的5种编程语言依然是Java、C、Python、C++、C#。C、Java、C++在近20年的时间里一直位居前三，直到C++被后起之秀Python在今年1月份顶出Top3。TIOBE官方作出预测，最快在今年年底前C语言或将成功逆袭Java，成为最热编程语言。
6984
2019-11-14 10:27:44
IT基础知识应该学什么？
作为IT行业的程序员必须掌握写必备的IT基础知识，例如数据储存、分布式存储架构、算法、云计算大数据、开发计算机语言、JAVA、工具、数据库、操作系统等知识。
13151
2019-11-20 11:55:48
未来有发展前景的IT技术岗位盘点
众所周知，在互联网时代，IT技术岗位是互联网公司和企业的核心发展力量。现在我们来盘点一下未来有发展前景的IT技术岗位。一般来说，IT技术岗位可以分为开发岗位、测试岗位、UI设计等，下面我将从这几个岗位的就业前景、应用领域和薪资待遇和大家讨论一下，这些岗位的发展前景到底怎么样。
6114
2019-11-26 10:00:16
低代码则低风险吗？事实并非如此
低代码/无代码工具提供支持拖放的交互界面,使得即使非程序员也能够创建或修改应用程序，而向非技术人员推出低代码/无代码产品带来的安全风险可能比用户了解到的更为复杂。
3469
2022-06-17 11:56:24
