在线客服
扫描二维码
下载博学谷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编程怎么样？
12136
2019-08-07 16:52:24
自学什么好找工作？学计算机怎么样？
自学什么好找工作？学计算机怎么样？首先小编认为自学需要结合自身的兴趣爱好和行业选择一个适合自己发展的行业，学什么可以听听别人的意见，目前互联网发展比较快，对于计算机方面的人才需求也比较大，但是并不缺初级程序员，如果学计算机就要做很大的决心。
7834
2019-08-13 11:37:30
IT编程入门门槛高吗？有哪些要求？
IT编程入门门槛高吗？有哪些要求？ 其实，学IT技术既不像一些培训机构鼓吹的那样适合任何人学习，也不像许多人担心的那样不适合数学或英语差的学习者入门。编程学习者可以来自各行各业，也可以完全没有基础从零开始学起。关键是要对IT编程有学习兴趣，并且有着持续的自学能力和出色的逻辑思维能力。下面我们来具体看看IT编程的入门要求。
12464
2020-03-13 18:33:37
学习编程有什么用？有哪些好处？
在这个互联网飞速发展，似乎人人都开始学习编程的时代，许多人心中还是有这样的疑问：学习编程有什么用？有哪些好处？诚然，大多数人学习编程的目的，都是想通过学习编程找到一份IT工程师的高薪工作。但是除了出于对这个行业的职位选择，我们学习编程到底有什么用呢？下面我们就来看一看，那些许多人都忽略的学习编程的好处和作用。
15787
2020-04-22 10:28:14
Linux学习环境搭建详解
在学习Linux环境搭建之前，我们首先简单了解一下什么是Linux。Linux其实有两种含义，一是我们通常说的广义上的操作系统，另外一种是由芬兰天才程序员托瓦兹编写的开源操作系统的内核。接下来我们要讲的内容涉及到的Linux，指的是广义上的操作系统。下面我们来看看学习Linux之前的环境准备、安装VirtualBox虚拟机、创建虚拟机以及在虚拟机中安装Linux系统相关内容。
7143
2020-06-23 19:05:57
