在线客服
扫描二维码
下载博学谷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接口管理工具有哪些？
相关推荐 更多
零基础计算机编程如何入门学习？没基础能学会吗？
互联网发展比较迅速，由于程序员新增待遇高，很多人想转型，那么零基础计算机编程如何入门？没基础能学会吗？大计算机科学比较专业，需要有些基础比如：c ，c++，离散数学，数据结构，数据库，软件工程，。零基础小白需要自修：Visual Basic、 Scripting、Frontpage， Flash。
9240
2019-05-30 09:38:22
程序员如何避免写出烂代码?
一个优秀的程序员应该要求自己尽量写出好代码，众所周知，好的代码应该符合逻辑清晰，易于维护，整洁简单，性能优化等优点。而完全与之相反的就是我们所说的烂代码。那么，我们应该如何避免写出烂代码呢？本文将为大家总结出十条避坑准则，希望可以帮助程序员们写出更加优美简洁的代码。
5394
2020-02-24 16:26:27
学IT需要具备什么条件？
随着IT人才在就业市场供小于求矛盾的凸显，IT行业的薪资待遇也水涨船高，其发展前景也是一片光明。因此，很多想了解，学IT需要具备什么条件？虽然，我们总说IT是一项现代社会人类必备的技能，但是确实有很多人学不好IT编程。究竟是天赋不足，还是其他什么原因？是不是学IT真的需要天才的大脑和异于常人的逻辑思维呢？下面我们一起来聊聊学IT需要具备的四大条件。
7533
2020-06-08 18:47:42
安卓编程入门学习要具备哪些能力？
随着安卓的不断发展壮大，安坐产品所占的市场份额也在不断扩张，全球安卓设备的使用量也不断提升，这也就导致安卓编程人才的需求量与日俱增，可以看出安卓编程的发展前景十分广阔。所以就有了许多人想要想要去学习安卓编程技术，那么安卓编程入门要具备那些能力，学什么？
3959
2020-06-16 15:53:06
未来互联网人才还稀缺吗？哪些技术方向热门？
未来互联网人才还稀缺吗？哪些技术方向热门？人才是最稀缺的资源，是实现百年卓越海亮的最关键要素，很多公司对专业人才的需求非常大，顶尖人才可以给公司带来很长远的收益。随着社会的不断发展越来越多的新职业也是不断的出现，随着社会的分工以及发展也会出现很多的紧缺的职业。
2845
2022-06-27 17:22:58
