在线客服
扫描二维码
下载博学谷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接口管理工具有哪些？
相关推荐 更多
如何学习计算机？新手小白入门须知
万事开头难，对于新手小白来讲计算机入门阶段是最迷茫无措的。其实学习任何新事物都是一样的，离不开为什么学？怎样学？这两大难题。新手在学习时首先应该有一个详细的学习计划，而不是头脑一热，这样才不容易轻易放弃。本文就来和大家谈谈“如何学习计算机”。
15609
2019-08-19 16:18:21
软件工程师要学哪些知识？难不难？
软件工程师要学哪些知识？难不难？作为互联网行业中最重要的技术岗位，软件工程师需要学习的内容十分广泛且深入，学习难度可想而知。当然，软件工程师也并不是大家想的那样十八班武艺样样精通。比如对英语水平的要求并不高，也不一定要学习多么深奥的数学知识。下面我们一起来看看想要成为一名合格的软件工程师需要学习的具体内容。
12924
2020-04-27 17:05:16
Android基础知识点面试复习整理
相信很多小伙伴在准备面试复习的时候，都会因为没有建立自己系统的知识结构，而常常翻开书本马冬梅，合上书本马什么梅。出现这样的情况并不是个例，因此大家应该努力建立自己的Android知识体系，这样多复习几遍，一些重难点就能了熟于胸了。本文为大家整理了一套全面的Android基础知识点，有面试复习需要的小伙伴赶紧收藏起来吧~
7031
2020-04-29 11:48:25
27岁转行学IT有前途吗？
27岁转行学IT有前途吗？常常可以在网上看到这些转业者的困惑。其实，到了27岁还想转业，无外乎就是之前的工作确实没有什么发展前途。而IT行业作为朝阳产业，发展前景好，一年以上的工作经验可以轻松找到上万薪资的岗位。最重要的是IT行业不看学历、性别和年纪，只要你的实力够硬，就不愁找不到工作。当然如果是35岁以后才开始学IT，那就要慎重了，毕竟精力和学习能力都比上二十多岁的年轻人了。
7019
2020-07-06 10:34:59
传智博学谷“狂野系列”在线课程成绩单喜人
传智博学谷“狂野系列”在线课程成绩单喜人，IT互联网行业发展快速，技能知识点更新迭代较快，程序员们保持学习才能在行业中具有核心竞争力。程序员为了寻求更高的职级和更好的待遇，采用最多的方式是学习热点技术。
3750
2022-04-19 13:51:40
