在线客服
扫描二维码
下载博学谷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行业目前蒸蒸日上的发展前景。对于想要入门编程的菜鸟来说，应该如何学习电脑程序呢？下面我们来详细看一看学习的指南。
7750
2020-01-10 11:30:52
计算机网络的基础概念讲解
随着互联网时代的深入发展，计算机网络的学习变得越来越重要了。目前IT行业已然是可以说是人人都想投身的热门行业，那么如果想要从事开发网络应用程序的相关岗位，深度了解计算机网络的基础概念和知识，可以说是必修的课程。下面本文将给大家讲解计算机网络的基础概念，具体包括定义、组成、核心内容和主要功能等内容。
5509
2020-03-09 15:38:29
计算机入门需要注意什么？
计算机入门需要注意什么？在这个信息化时代，很多行业的办公需求都离不开计算机，尤其是随着高科技不断入驻各行各业，市面上对人才的需求量也越来越大，很多人都想要跻身互联网行业，但是计算机入门难吗？入门计算机之前需要注意些什么呢？
3999
2020-06-02 14:21:34
自学IT编程怎么找编程资料？
自学IT编程怎么找编程资料？选择做程序员就需要一颗保持学习的心，因为技术更新快、需求变化快等原因，所以得时刻保持学习才能不被淘汰。正因为如此，程序员一般都要有一些自学能力，说到自学，就出现了“如何找到自己想要的编程资源”的问题了，接下来我们就一起去了解了解吧。
5105
2020-06-17 15:52:20
2020年程序员平均薪资新鲜出炉
根据最新的2020年程序员平均工资统计，全国有313739人从事程序员岗位，其中平均工资在14K左右，而全国大部分的程序员薪资待遇都在5K~35K之间，可以看到根据地区经济的发展水平和个人的能力水平，程序员之间的薪资待遇还是存在较大差异。下面一起来看看新鲜出炉的2020年程序员平均薪资分析。
6031
2020-06-26 17:40:55
