在线客服
扫描二维码
下载博学谷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接口管理工具有哪些？
相关推荐 更多
学IT编程的女生就业前景如何？
学IT编程的女生就业前景如何？学IT编程的女生就业方向有很多，总的来说IT行业就业前景广阔，学IT编程的女生毕业后可以去做平面设计、Web前端开发、网站运维、SEO、网络推广、电商运营、微信运营等，这些职位女生都是可以去做，根据个人兴趣和学习情况去选择。
8582
2019-08-07 17:57:21
IT编程培训一年多少钱？
IT编程培训一年多少钱？首先IT编程培训的科目有很多，目前比较主流热门的科目一般有Java、Python、前端、大数据、运维、软件测试等等。考察市面上的多家IT培训机构，我们大概可以发现线下的培训费用一般都在15K~25K，根据学习科目的不同，价格也会有一些差异。不过除了学费，还有许多朋友是离开家乡来参加培训的，因此还要加上住宿和生活费，因此IT编程培训一年的花费会更大。
12214
2020-04-10 15:27:07
自学编程入门有哪些困难？
许多人是0基础，想要自学编程入门，在学期前期就会遇到许多的困难和迷茫。例如不知道从什么语言开始，也不清楚自己的目标是什么，对于毫无基础的初学者来着，无疑是非常困难的。
4898
2020-05-28 15:55:37
计算机网络常用术语大全
随着互联网技术岗位的走俏，越来越多的零基础转行者开始学习计算机技术。因此，小编为初学者整理汇总了计算机网络常用术语大全，大家在入门IT编程之前，可以简单对计算机的基础术语有一个大致的了解，从而为后续的学习奠定基础。下面一起来看看详细内容吧~
5918
2020-07-28 16:15:21
程序员能拿多少工资
边上班，边学习，安安静静地学技术，长本事，待时机成熟时，跳槽拿更高offer。或许是工作2~5年的程序员们，非常希望达成的一件事了。
2986
2022-09-30 16:54:05
