在线客服
扫描二维码
下载博学谷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接口管理工具有哪些？
相关推荐 更多
零基础软件编程入门自学要学什么？
在移动互联网时代，软件编程自然成为了热门职业。不少零基础、零经验的人想学软件编程，不免有这样的提问：零基础软件编程入门自学要学什么？小编在这里一次性给大家答疑解惑。
14785
2019-07-10 13:29:54
IT行业的发展前景好不好？有哪些发展趋势？
IT行业的发展前景好不好？有哪些发展趋势？随着近些年来，中国互联网和通信技术的提升速度不断加快，IT市场的需求也随之不断增大。同时，IT工作也将变得更加具有挑战性，企业对IT技术人才的需要主要集中在中高级的IT工程师上。因此IT行业的发展前景不言而喻，下面我们来具体看一看未来IT行业的发展趋势。
9014
2020-02-10 13:54:55
IT学习一般会有哪些课程？
IT培训的课程种类很多，主要分为开发类、测试类、营销类、设计类、运维类几大类，开发类包括前端开发、和后端开发，后端开发又包含Java开发、大数据、Python开发，设计类包含UI设计、AR/VR游戏设计，运维类包括Linux运维、网络安全，剩下还有软件测试以及互联网营销。
5890
2020-06-16 15:02:18
编程零基础如何学好Linux？
首先大家要明白Linux入门不难，但是到精通的水平难度确实很高，而且它学习曲线陡峭，因此很多初学者很容易就迷失了学习方向和思路。那么，编程零基础如何学好Linux呢？下面我们来一起看看Linux的学习方法和学习内容，希望可以帮助还没入门的初学者，快速上手Linux。
5094
2020-07-14 16:44:51
编程初学者怎么选择学科？学什么好？
编程初学者怎么选择学科？编程语言是一种计算机和人都能识别的语言。编程语言有Java、 JavaScript、 Python、C、C#、C++、PHP、0C、 Swift、Go、 Scala、R等。互联网的发展对技术、程序员的需求逐渐增大，很多人想转行从事计算机编程工作，编程语言众多选择学什么成了大家关心的问题。
5672
2020-08-20 17:12:53
