在线客服
扫描二维码
下载博学谷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接口管理工具有哪些？
相关推荐 更多
Java和C语言有什么区别？学哪个语言好就业？
Java和C语言都是现阶段IT行业里被广泛使用的编程语言，说起它们之间的区别还是相当大的。许多编程语言的初学者在学习初期，都会遇到这样的问题，Java和C语言学哪个语言好就业？其实只要你学好其中随意一门，就业就都不会有太大的问题。如果非要比较Java和C语言的就业前景，从目前的行业形势分析，选择学Java的话你的职业发展方向更多，高薪的就业机会也越大。
8015
2019-11-29 14:43:23
如何优化if-else代码结构？
不少人在学习编程的时候都会遇到这样的疑惑：如何优化if-else代码结构？为了解决大家的这个学习障碍，本文以<输出今天为星期几> 来聊聊优化if-else代码结构的具体步骤。虽然每个项目都有不同的复杂情况，但是优化思路和逻辑都是一样，大家掌握了本文优化if-else代码结构的方法就可以举一反三，完成更复杂代码的优化。感兴趣的朋友赶紧看下去吧！
4813
2020-04-03 18:31:48
哪些IT编程入门书籍比较好？
哪些IT编程入门书籍比较好？许多东西在没有基础的情况下，学习起来是具有一定难度的。如果选择自学，在书籍的选择上需要有正确的方向与指导。书对于编程入门都是有非常大帮助的，熟练学习和掌握了这些书籍的知识内容。
5958
2020-06-08 14:01:02
学习编程之前需要掌握哪些基础知识
学习编程之前需要掌握哪些基础知识，学习编程需要一个系统的过程，掌握操作系统体系结构、计算机网络、数据库等方面的知识。有一定基础后入门和上手更容易些。可以在学习编程语言的过程中同步学习，另外学习编程还需要重点学习一下算法设计和数据结构。
13057
2020-06-08 14:46:39
怎样写一份让面试官眼前一亮的简历
项目经验里面不要只是写项目的业务模块，要把这个项目里面所用到的技术栈给写进去。 比如说用到的开发框架、中间件。因为这些技术点如果只是写在前面的个人能力部分，很可能给人一种你只是在堆技术，而对于这些技术并没有真实的应用到项目中去。
2541
2022-10-07 18:15:52
