在线客服
扫描二维码
下载博学谷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接口管理工具有哪些？
相关推荐 更多
免费软件编程入门自学视频有哪些？
对于想要自学软件编程入门的小伙伴来讲，最主要的学习方式莫过于观看视频了。通过这种方式自学，不仅可以增加学习的趣味性，还能使同学们更加便捷直观的掌握知识。那么免费软件编程入门自学视频有哪些？下面让小编为大家一一介绍：
9156
2019-08-16 18:42:51
3G软件工程师培训学什么？学多久可以就业？
3G软件工程师作为目前的黄金岗位，无论是从职位的招聘需求还是薪资待遇考虑，其就业前景都是无可限量的。也正因如此，不少人都关注起了3G软件工程师培训。那么，3G软件工程师培训学什么？学多久可以就业？简单来讲，编程语言和通信相关知识都是需要学习的重点，下面我们具体看一下培训的内容。至于学习的时间要根据学习者自身的能力水平和努力程度决定。
6361
2020-02-03 17:01:13
程序员这个岗位可以干多少年？
程序员作为当前高薪且极具发展前途的热门岗位，吸引了许多人的青睐。然而也有一些人担心程序员只是一个吃青春饭的岗位，到了30岁以后就会失去竞争力。实际上，这完全是大众对于这个行业存在普遍误解。虽然，一个程序员的编程能力和编程年纪不一定成正比，但是在绝大多数的情况下，参与更多项目开发经验的资深程序员一定比年轻的程序员更吃香。下面我们来详细看看程序员这个岗位可以干多少年。
5594
2020-02-28 13:43:05
互联网研发岗位面试指南
因为疫情的影响，今年比往年的面试环境更加残酷。互联网研发岗位一向是各大企业公司需求的核心岗位，因此从这个角度来讲，研发岗位的求职者仍旧有着许多的机会。那么，大家应该如何准备面试把握好机会呢？本文将从考核重点、专业准备、项目介绍和远程面试注意事项几个重点，为大家呈现上一份详细的互联网研发岗位面试指南。
4385
2020-04-13 15:13:28
IT程序员是干什么的？
随着近些年来，互联网爆炸式的增长和发展，程序员作为一个技术职业，越来越为大众所熟悉。一般来讲，我们把从事软件开发设计工作的人叫做程序员，因此IT程序员其实是一个很大范围的职业统称。那么，IT程序员是干什么的呢？下面我们一起来看看IT程序员的具体分类和工作内容。
6859
2020-06-15 11:18:59
