前言
二分查找作为程序员的一项基本技能，是面试官最常使用来考察程序员基本素质的算法之一，也是解决很多查找类题目的常用方法，它可以达到O(log n)的时间复杂度。
一般而言，当一个题目出现以下特性时，你就应该立即联想到它可能需要使用二分查找：
- 待查找的数组有序或者部分有序
- 要求时间复杂度低于O(n)，或者直接要求时间复杂度为O(log n)
二分查找有很多种变体，使用时需要注意查找条件，判断条件和左右边界的更新方式，三者配合不好就很容易出现死循环或者遗漏区域，本篇中我们将介绍常见的几种查找方式的模板代码，包括：
- 标准的二分查找
- 二分查找左边界
- 二分查找右边界
- 二分查找左右边界
- 二分查找极值点
本文的内容来自于笔者个人的总结，事实上二分查找有很多种等价的写法，本文只是列出了笔者认为的最容易理解和记忆的方法。
标准二分查找
首先给出标准二分查找的模板：
class BinarySearch {
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = left + ((right - left) >> 1);
if (nums[mid] == target) return mid;
else if (nums[mid] > target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return -1;
}
}
- 循环条件：
left <= right - 中间位置计算：
mid = left + ((right -left) >> 1) - 左边界更新：
left = mid + 1 - 右边界更新：
right = mid - 1 - 返回值：
mid / -1
这里有几点需要注意：
我们的循环条件中包含了
left == right的情况，则我们必须在每次循环中改变left和right的指向，以防止进入死循环-
循环终止的条件包括：
- 找到了目标值
-
left > right（这种情况发生于当left, mid, right指向同一个数时，这个数还不是目标值，则整个查找结束。）
left + ((right -left) >> 1)其实和(left + right) / 2是等价的，这样写的目的一个是为了防止(left + right)出现溢出，一个是用右移操作替代除法提升性能。-
left + ((right -left) >> 1)对于目标区域长度为奇数而言，是处于正中间的，对于长度为偶数而言，是中间偏左的。因此左右边界相遇时，只会是以下两种情况：-
left/mid,right(left, mid 指向同一个数，right指向它的下一个数) -
left/mid/right（left, mid, right 指向同一个数）
-
即因为mid对于长度为偶数的区间总是偏左的，所以当区间长度小于等于2时，mid 总是和 left在同一侧。
实战1：Guess Number Higher or Lower
- leetcode 原题： https://leetcode.com/problems...
- 难度等级： Easy
We are playing the Guess Game. The game is as follows:
I pick a number from 1 to n. You have to guess which number I picked.
Every time you guess wrong, I'll tell you whether the number is higher or lower.
You call a pre-defined API guess(int num) which returns 3 possible results (-1, 1, or 0):
-1 : My number is lower
1 : My number is higher
0 : Congrats! You got it!
Example :Input: n = 10, pick = 6
Output: 6
这题基本是可以直接照搬二分查找的，出题者没有做任何包装，我们直接使用标准二分查找：
public class Solution extends GuessGame {
public int guessNumber(int n) {
int left = 1;
int right = n;
while (left <= right) {
int mid = left + ((right - left) >> 1);
if (guess(mid) == 0) {
return mid;
} else if (guess(mid) == -1) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return -1;
}
}
实战2：Sqrt(x)
- leetcode 原题： https://leetcode.com/problems...
- 难度等级： Easy
Implement int sqrt(int x).
Compute and return the square root of x, where x is guaranteed to be a non-negative integer.
Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.
这一题其实是二分查找的应用，乍一看好像和二分查找没有关系，但是我们可以用二分查找的思想快速定位到目标值的平方根，属于二分查找的一个简单运用：
class Solution {
public int mySqrt(int x) {
if (x <= 1) return x;
int left = 1;
int right = x - 1;
while (left <= right) {
int mid = left + ((right - left) >> 1);
if (mid > x / mid) {
right = mid - 1;
} else if (mid < x / mid) {
if (mid + 1 > x / (mid + 1)) return mid;
left = mid + 1;
} else {
return mid;
}
}
return -1; // only for return a value
}
}
虽然是简单的题目，但是还是要注意对溢出的处理，例如我们使用 mid > x / mid 而不是 mid * mide > x 作为判断条件，因为后者可能会导致溢出，这与我们使用 left + ((right - left) >> 1) 而不是 (left + right) / 2 作为mid的值是一个道理，这是因为 left + right 也可能溢出。
二分查找左边界
利用二分法寻找左边界是二分查找的一个变体，应用它的题目常常有以下几种特性之一：
- 数组有序，但包含重复元素
- 数组部分有序，且不包含重复元素
- 数组部分有序，且包含重复元素
左边界查找类型1
类型1包括了上面说的第一种，第二种情况。
既然要寻找左边界，搜索范围就需要从右边开始，不断往左边收缩，也就是说即使我们找到了nums[mid] == target, 这个mid的位置也不一定就是最左侧的那个边界，我们还是要向左侧查找，所以我们在nums[mid]偏大或者nums[mid]就等于目标值的时候，继续收缩右边界，算法模板如下：
class Solution {
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid;
}
}
return nums[left] == target ? left : -1;
}
}
- 循环条件：
left < right - 中间位置计算：
mid = left + ((right -left) >> 1) - 左边界更新：
left = mid + 1 - 右边界更新：
right = mid - 返回值：
nums[left] == target ? left : -1
与标准的二分查找不同：
首先，这里的右边界的更新是right = mid，因为我们需要在找到目标值后，继续向左寻找左边界。
其次，这里的循环条件是left < right。
因为在最后left与right相邻的时候，mid和left处于相同的位置(前面说过，mid偏左)，则下一步，无论怎样，left, mid, right都将指向同一个位置，如果此时循环的条件是left <= right，则我们需要再进入一遍循环，此时，如果nums[mid] < target还好说，循环正常终止；否则，我们会令right = mid，这样并没有改变left,mid,right的位置，将进入死循环。
事实上，我们只需要遍历到left和right相邻的情况就行了，因为这一轮循环后，无论怎样，left,mid,right都会指向同一个位置，而如果这个位置的值等于目标值，则它就一定是最左侧的目标值；如果不等于目标值，则说明没有找到目标值，这也就是为什么返回值是nums[left] == target ? left : -1。
左边界查找类型2
左边界查找的第二种类型用于数组部分有序且包含重复元素的情况，这种条件下在我们向左收缩的时候，不能简单的令 right = mid，因为有重复元素的存在，这会导致我们有可能遗漏掉一部分区域，此时向左收缩只能采用比较保守的方式，代码模板如下：
class Solution {
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid;
} else {
right--;
}
}
return nums[left] == target ? left : -1;
}
}
它与类型1的唯一区别就在于对右侧值的收缩更加保守。这种收缩方式可以有效地防止我们一下子跳过了目标边界从而导致了搜索区域的遗漏。
关于这种类型的例子，可以看下面的实战5。
实战3：First Bad Version
- leetcode 原题： https://leetcode.com/problems...
- 难度等级： Easy
这道题的题目比较长，原题就不贴了，大意就是说：有这么一个数组：
[false, false, false, ..., fasle, true, true, ..., true]
求最左侧的那个true的位置。
这就是一个典型的查找左边界的问题：数组中包含重复元素，我们需要找到最左侧边界的位置。直接使用二分查找左边界的模板就行了：
public class Solution extends VersionControl {
public int firstBadVersion(int n) {
int left = 0;
int right = n - 1;
while (left < right) {
int mid = left + ((right - left) >> 1);
if (!isBadVersion(mid + 1)) {
left = mid + 1;
} else {
right = mid;
}
}
return isBadVersion(left + 1) ? left + 1 : -1;
}
}
与之类似的例子还有：LeetCode 744 等，都是Easy级别的题目，简单的使用二分查找左边界的模板就行了，大家可以自行练习。
当然，除了这种显而易见的题目，对于一些变体，我们也应该要有能力去分辨，比如说这一题：LeetCode 658 。
实战4：Find Minimum in Rotated Sorted Array
- leetcode 原题： https://leetcode.com/problems...
- 难度等级： Medium
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).
Find the minimum element.
You may assume no duplicate exists in the array.
这一题看上去没有重复元素，但是它也是查找左边界的一种形式，即可以看做是查找旋转到右侧的部分的左边界，有了这个思想，直接用二分查找左边界的模板就行了：
class Solution {
public int findMin(int[] nums) {
if (nums.length == 1) return nums[0];
int left = 0;
int right = nums.length - 1;
while (left < right) {
int mid = left + ((right - left) >> 1);
if (nums[mid] > nums[nums.length - 1]) {
left = mid + 1;
} else {
right = mid;
}
}
return nums[left];
}
}
实战5：Find Minimum in Rotated Sorted Array II
- leetcode 原题： https://leetcode.com/problems...
- 难度等级： Hard
这道题目和上面的实战2类似，只是多了一个条件——数组中可能包含重复元素，这就是我们之前说的二分查找左边界的第二种类型，在这种情况下，我们只能采用保守收缩的方式，以规避重复元素带来的对于单调性的破坏：
class Solution {
public int findMin(int[] nums) {
if (nums.length == 1) return nums[0];
int left = 0;
int right = nums.length - 1;
while (left < right) {
int mid = left + ((right - left) >> 1);
if (nums[mid] > nums[right]) { // mid 位于旋转点左侧
left = mid + 1;
} else if (nums[mid] < nums[right]) { // mid 位于旋转点右侧
right = mid;
} else {
// 注意相等的时候的特殊处理，因为要向左查找左边界，所以直接收缩右边界
right--;
}
}
return nums[left];
}
}
二分查找右边界
有了寻找左边界的分析之后，再来看寻找右边界就容易很多了，毕竟左右两种情况是对称的嘛，关于使用场景这里就不再赘述了，大家对称着理解就好。我们直接给出模板代码：
class Solution {
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left < right) {
int mid = left + ((right - left) >> 1) + 1;
if (nums[mid] > target) {
right = mid - 1;
} else {
left = mid;
}
}
return nums[right] == target ? right : -1;
}
}
- 循环条件：
left < right - 中间位置计算：
mid = left + ((right -left) >> 1) + 1 - 左边界更新：
left = mid - 右边界更新：
right = mid - 1 - 返回值：
nums[right] == target ? right : -1
这里大部分和寻找左边界是对称着来写的，唯独有一点需要尤其注意——中间位置的计算变了，我们在末尾多加了1。这样，无论对于奇数还是偶数，这个中间的位置都是偏右的。
对于这个操作的理解，从对称的角度看，寻找左边界的时候，中间位置是偏左的，那寻找右边界的时候，中间位置就应该偏右呗，但是这显然不是根本原因。根本原因是，在最后left和right相邻时，如果mid偏左，则left, mid指向同一个位置，right指向它们的下一个位置，在nums[left]已经等于目标值的情况下，这三个位置的值都不会更新，从而进入了死循环。所以我们应该让mid偏右，这样left就能向右移动。这也就是为什么我们之前一直强调查找条件，判断条件和左右边界的更新方式三者之间需要配合使用。
右边界的查找一般来说不会单独使用，如有需要，一般是需要同时查找左右边界。
二分查找左右边界
前面我们介绍了左边界和右边界的查找，那么查找左右边界就容易很多了——只要分别查找左边界和右边界就行了。
实战6: Find First and Last Position of Element in Sorted Array
- leetcode 原题： https://leetcode.com/problems...
- 难度等级： Medium
Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.
Your algorithm's runtime complexity must be in the order of O(log n).
If the target is not found in the array, return [-1, -1].
这是一道特别标准的查找左右边界的题目，我们只需要分别查找左边界和右边界就行了：
class Solution {
public int[] searchRange(int[] nums, int target) {
int[] res = new int[]{-1, -1};
if(nums == null || nums.length == 0) return res;
// find the left-end
int left = 0;
int right = nums.length - 1;
while (left < right) {
int mid = left + ((right - left) >> 1);
if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid;
}
}
res[0] = nums[left] == target ? left : -1;
// find right-end
if (res[0] != -1) {
if (left == nums.length - 1 || nums[left + 1] != target) {
res[1] = left;
} else {
right = nums.length - 1;
while (left < right) {
int mid = left + ((right - left) >> 1) + 1;
if (nums[mid] > target) {
right = mid - 1;
} else {
left = mid;
}
}
res[1] = right;
}
}
return res;
}
}
二分查找极值
二分查找还有一种有趣的变体是二分查找极值点，之前我们使用nums[mid]去比较的时候，常常是和给定的目标值target比，或者和左右边界比较，在二分查找极值点的应用中，我们是和相邻元素去比，以完成某种单调性的检测。关于这一点，我们直接来看一个例子就明白了。
实战7：Find Peak Element
- leetcode 原题：https://leetcode.com/problems...
- 难度等级： Medium
A peak element is an element that is greater than its neighbors.
Given an input array nums, where nums[i] ≠ nums[i+1], find a peak element and return its index.
The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.
You may imagine that nums[-1] = nums[n] = -∞.
这一题的有趣之处在于他要求求一个局部极大值点，并且整个数组不包含重复元素。所以整个数组甚至可以是无序的——你可能很难想象我们可以在一个无序的数组中直接使用二分查找，但是没错！我们确实可以这么干！谁要人家只要一个局部极大值即可呢。
class Solution {
public int findPeakElement(int[] nums) {
int left = 0;
int right = nums.length - 1;
while (left < right) {
int mid = left + ((right - left) >> 1);
if (nums[mid] < nums[mid + 1]) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
}
这里尤其注意我们的判断条件nums[mid] < nums[mid + 1]，这实际上是在判断处于mid处的相邻元素的单调性。
总结
除了本文所介绍的二分查找的应用方式，二分查找其实还有很多其他的变体和应用，但它们基本上是循环条件，判断条件，边界更新方法的不同组合，例如，有的二分查找的循环条件可以是 while(left + 1 < right)，有的边界的更新的条件需要依赖 nums[left], nums[mid], nums[mid+1], nums[right]四个值的相互关系。
但是无论如何，代码模板只是给大家一个理解问题的角度，生搬硬套总是不好的。实际应用中，我们只要记住循环条件，判断条件与边界更新方法三者之间的配套使用就行了，基于这一点原则，你就可以使用你自己习惯的方式来实现二分搜索。
但是，如果你真的只是想应付面试，我想下面这个表的总结应该就差不多足够用了：
| 查找方式 | 循环条件 | 左侧更新 | 右侧更新 | 中间点位置 | 返回值 |
|---|---|---|---|---|---|
| 标准二分查找 | left <= right |
left = mid - 1 |
right = mid + 1 |
(left + right) / 2 |
-1 / mid |
| 二分找左边界 | left < right |
left = mid - 1 |
right = mid |
(left + right) / 2 |
-1 / left |
| 二分找右边界 | left < right |
left = mid |
right = mid - 1 |
(left + right) / 2 + 1 |
-1 / right |
最后，希望大家在理解二分查找的思想后都能够写出适合自己的搭配方式，共勉！
(完)
