【数据结构与算法基础】代码仓库：https://github.com/jinrunheng/datastructure-and-algorithm
一：二分查找法
在上一章节，我们介绍了线性查找法，线性查找法是一个 O(n) 级别的算法。本章节我们将介绍一种 O(logn) 级别的查找算法——二分查找法。
二分查找法（Binary Search）也被称作折半查找法，它是一种效率较高的查找算法，但是使用二分查找法的前提是待查找的数列必须是一个有序数列。也就是说，排序是二分查找法的前置条件。
二分查找的原理也非常简单：
我们要在一个有序数组 arr 中寻找一个目标值 target 的位置，首先我们定位到数组最中间的位置，如果我们的目标值 target 比中间的那个数字 v 还要小，我们就在 v 左边部分继续寻找；如果我们的目标值 target 比中间的那个数字 v 还要大，我们就在 v 右边部分继续寻找。很容易地就可以想到，这是其实就是一个递归的过程。
那二分查找法的时间复杂度是多少呢？
我们每一次定位到有序数组的中点，并且让目标值与中点值进行比较，如果找到了我们就直接返回结果，如果没有找到，那目标值不是在以中点值作为划分的左半边就是以中点值作为划分的右半边，换句话说，每一次，我们都可以砍掉一半的数据。所以，二分查找法的时间复杂度实际上就是对有序数组的个数 n 不停地除 2，直至找到目标值的次数，也就是 O(logn)。
二分查找法的思想看上去非常简单，不过实现起来需要注意很多的细节。值得一提的是，二分查找的思想在 1946 年被 John Mauchly 提出，直至 1962 年，才出现了第一个没有 bug 的二分查找算法的实现，中间整整隔了 16 年 ：）。
二分查找法的递归实现
二分查找法的递归实现非常的简单，在这里就不再赘述了，大家可以点击链接进行查看。
我们直接来看一下 LeetCode 的 704 号问题：704. 二分查找 递归写法的代码：
二分查找法的非递归实现
二分查找法的非递归实现大家可以点击链接进行查看，这里面我仍然对 LeetCode 704 号问题进行求解，代码如下所示：
修改循环不变量的定义实现二分查找法
在我们之前的代码，我们是在 nums[l,r] 前闭后闭的范围中寻找 target。
这一次，我们修改循环不变量的定义，在 nums[l,r) 前闭后开的范围中寻找 target，来实现我们的二分查找法。
依旧是以 LeetCode 704 号问题进行求解，代码如下所示：
我们可以通过上面的代码看到，当我们的二分查找法的循环不变量的定义发生改变时，代码逻辑也会发生改变，不过，这些改变仍然会紧紧围绕着循环不变量，维持着循环不变量的定义，保证前后逻辑的一致性，这一点请大家用心体会。
二：二分查找法的变种
upper
譬如这样一个例子：
上图给出的是一个班学生的已经排过序的成绩，老师想要知道超出及格线的最小的分数是多少。
毫无疑问，这个问题自然也可以使用二分查找法来解决。
该问题的本质是，查找大于 target 的最小值，这样一类问题，我们叫做二分查找法的一类变种：upper。
三：二分查找法的相关习题
若有收获，就点个赞吧
0 人点赞
