在线客服
扫描二维码
下载博学谷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接口管理工具有哪些？
相关推荐 更多
抓取App攻略 手把手的步骤指导
现在的社会智能手机已经全面普及，而随之产生改变的还有应用软件（APP）取代网页，成为主流的技术。由于APP的内容一度无法被搜索引擎抓取到，移动互联网将带来一场搜索引擎的生存危机。不过，通过和应用软件开发商的合作，已经一定程度上化解了这场危机。现在，小编整理了抓取App的全面攻略，手把手指导大家如何一步一步操作。
8203
2019-12-05 14:27:14
如何学习计算机技术？自学计算机还是报班？
自学计算机还是报班？首先明确学习计算机的目标，找到适合自己的学习方法，有个积极的学习态度，如果自己学习能力较强自制力好可以通过自学，相反，基础差学习能力弱建议选择计算机培训班学习。
8198
2020-01-17 16:38:12
一名优秀的程序员需要具备的六大素质
随着IT行业的发展，程序员这一岗位受到了众多人的青睐和追捧。然而许多不是科班出身朋友在考虑学习IT技术并转行前，都会思考这样一个问题：自己到底适不适合做程序员呢？其实这个问题的答案很简单，人人都可以学习IT编程，但是要成为一名优秀的程序员需要具备以下六大素质。
8308
2020-02-14 18:06:55
编程难学吗？如何自学编程？
近些年的薪资排行榜上，金融和IT行业连续多年稳居前二，IT作为互联网最中坚，最核心的行业，一直吸引很多人的加入。而编程作为IT最核心的岗位，更是引起了很多人的关注，编程的学习难度如何？怎样自学编程？
4949
2020-06-01 16:44:25
0基础IT学习容易吗？应该怎样学习？
IT学习容易吗？应该怎样学习？IT行业蓬勃发展，现在很多小伙伴都想学习IT知识，成为一名IT行业工作者。但是往往开始学习之前又会有很多顾虑，担心自己是完全零经验的小白，会有“学习起来容易吗”，“应该怎么进行学习呢”，“现在开始学晚吗”等诸多疑问。
5905
2020-06-08 10:58:28
