在线客服
扫描二维码
下载博学谷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接口管理工具有哪些？
相关推荐 更多
软件编程入门自学要学什么？零基础小白学习路线
软件编程入门自学要学什么？零基础小白需要从计算机的一些基础原理学起。总体上来看，学习的内容比较多，包括数字电路、计算机组成原理、汇编语言、计算机操作系统、计算机编译原理、离散数学、数据结构与算法、计算机网络等。本文将详细为大家讲讲零基础小白学习路线。
9947
2019-08-30 12:10:47
学习编程入门先学什么？
学习编程入门，先学什么？其实对于编程来说，任何一个你能持之以恒学习的编程语言都行，今天呢，小编想分享一个编程入门书单，希望大家通过这些书来找到自己的学习方法。
6331
2020-04-01 17:49:22
怎样选择培训课堂才能事半功倍
许多人在选择培训机构之前，都会遇到许多迷茫的问题。线上培训和线下培训的区别；不同的培训风格是否会产生不同的影响，侧重点是否会存在误差；许多培训的起点也不同，这些问题带来的困扰不在少数，那么该如何做出选择呢？
4172
2020-05-19 09:41:56
程序员培训机构哪个好？哪家靠谱？
程序员培训机构哪个好？受疫情影响身边的小伙伴大学毕业便是失业，开始了人生的迷茫期，毕业后没有一技之长，招工作成了难题，想获得高薪不少人想入行IT行业，但需要多方面考察选择靠谱的IT程序员培训机构，遇到不靠谱的培训机构会学无所成，还打击自己学习的兴趣。
7260
2020-07-03 14:39:15
OSI参考模型有多少层？
OSI参考模型是由 ISO(国际标准化组织）制定的，它的作用是提供给开发者一个必须的、通用的概念以便开发完善、可以用来解释连接不同系统的框架。OSI参考模型将计算机网络体系结构划分为以下七层：应用层、表示层、会话层、传输层、网络层、数据链路层以及物理层。网络模型为什么有这么多的层？这些层的作用是什么，它们到底是干什么用的？下面我们就一起来看看吧！
6213
2020-08-11 10:55:08
