学到了吗（二分查找递归算法代码）二分查找递归实现，Java数据结构算法之二分查找详解：二分查找框架和基本的二分搜索，java二分查找，

先给⼤家讲个笑话乐呵⼀下： 有⼀天阿东到图书馆借了 N 本书，出图书馆的时候，警报响了，于是保安 把阿东拦下，要检查⼀下哪本书没有登记出借。阿东正准备把每⼀本书在报 警器下过⼀下，以找出引发警报的书，但是保安露出不屑的眼神：你连⼆分查找都不会吗？于是保安把书分成两堆，让第⼀堆过⼀下报警器，报警器 响；于是再把这堆书分成两堆…… 最终，检测了 logN 次之后，保安成功的 找到了那本引起警报的书，露出了得意和嘲讽的笑容。于是阿东背着剩下的 书⾛了。

从此，图书馆丢了 N - 1 本书。

⼆分查找并不简单，Knuth ⼤佬（发明 KMP 算法的那位）都说⼆分查找： 思路很简单，细节是魔⿁。很多⼈喜欢拿整型溢出的 bug 说事⼉，但是⼆分 查找真正的坑根本就不是那个细节问题，⽽是在于到底要给 mid 加⼀还是 减⼀，while ⾥到底⽤ <= 还是 < 。

下面我们先说二分查找框架。

一、分析⼆分查找的技巧

分析⼆分查找的⼀个技巧是：不要出现 else，⽽是把所有情况⽤ else if 写清楚，这样可以清楚地展现所有细节。本⽂都会使⽤ else if，旨在讲清楚，读者理解后可⾃⾏简化。 其中 ... 标记的部分，就是可能出现细节问题的地⽅，当你⻅到⼀个⼆分 查找的代码时，⾸先注意这⼏个地⽅。后⽂⽤实例分析这些地⽅能有什么样 的变化。

另外声明⼀下，计算 mid 时需要防⽌溢出，代码中 left + (right - left) / 2 就和 (left + right) / 2 的结果相同，但是有效防⽌了 left 和 right 太⼤直接相加导致溢出。

二、寻找⼀个数（基本的⼆分搜索）

这个场景是最简单的，肯能也是⼤家最熟悉的，即搜索⼀个数，如果存在， 返回其索引，否则返回 -1。

1、为什么 while 循环的条件中是 <=，⽽不是 <？

答：因为初始化 right 的赋值是 nums.length - 1 ，即最后⼀个元素的索 引，⽽不是 nums.length 。

这⼆者可能出现在不同功能的⼆分查找中，区别是：前者相当于两端都闭区 间 [left, right] ，后者相当于左闭右开区间 [left, right) ，因为索引⼤⼩为 nums.length 是越界的。 我们这个算法中使⽤的是前者 [left, right] 两端都闭的区间。这个区间其实就是每次进⾏搜索的区间。

什么时候应该停⽌搜索呢？当然，找到了⽬标值的时候可以终⽌：

但如果没找到，就需要 while 循环终⽌，然后返回 -1。那 while 循环什么时 候应该终⽌？搜索区间为空的时候应该终⽌，意味着你没得找了，就等于没找到嘛。

while(left <= right) 的终⽌条件是 left == right + 1 ，写成区间的形式就是 [right + 1, right] ，或者带个具体的数字进去 [3, 2] ，可⻅这时候区间为空，因为没有数字既⼤于等于 3 ⼜⼩于等于 2 的吧。所以这时候while 循环终⽌是正确的，直接返回 -1 即可。

while(left < right) 的终⽌条件是 left == right ，写成区间的形式就是 [left, right] ，或者带个具体的数字进去 [2, 2] ，这时候区间⾮空，还有⼀个数 2，但此时 while 循环终⽌了。也就是说这区间 [2, 2] 被漏掉了，索引 2 没有被搜索，如果这时候直接返回 -1 就是错误的。 当然，如果你⾮要⽤ while(left < right) 也可以，我们已经知道了出错的原因，就打个补丁好了：

2、为什么 left = mid + 1 ， right = mid - 1 ？

我看有的代码是 right = mid 或者 left = mid ，没有这些加加减减，到底怎么回事，怎么判断？

答：这也是⼆分查找的⼀个难点，不过只要你能理解前⾯的内容，就能够很 容易判断。 刚才明确了「搜索区间」这个概念，⽽且本算法的搜索区间是两端都闭的， 即 [left, right] 。那么当我们发现索引 mid 不是要找的 target 时，下⼀步应该去搜索哪⾥呢？

当然是去搜索 [left, mid-1] 或者 [mid+1, right] 对不对？因为 mid 已经搜索过，应该从搜索区间中去除。

3、此算法有什么缺陷？

答：⾄此，你应该已经掌握了该算法的所有细节，以及这样处理的原因。但是，这个算法存在局限性。

⽐如说给你有序数组 nums = [1,2,2,2,3] ， target 为 2，此算法返回的索引是 2，没错。但是如果我想得到 target 的左侧边界，即索引 1，或者我想得到 target 的右侧边界，即索引 3，这样的话此算法是⽆法处理的。

这样的需求很常⻅，你也许会说，找到⼀个 target，然后向左或向右线性搜索不⾏吗？可以，但是不好，因为这样难以保证⼆分查找对数级的复杂度了。

我们后续的算法就来讨论这两种⼆分查找的算法。 如需左神算法全套及数据结构算法体系课程请点击进入即可，也可私信索取。