减治思想——二分查找详细总结
减治思想——二分查找详细总结
二分查找应用于有序数组，可以在以\(O(\log(n))\)时间复杂度进行查找。其思想在于利用数组的有序性直接排除掉一些元素，这也是进行“减治”的地方。二分查找思想看起来简单，但是其边界条件其实很容易弄混，下面就对各种情况的二分查找（基础情形、左边界二分查找、右边界二分查找、应插入位置二分查找）进行详细的说明，完整的代码附在附录里面。
文章的的后半部分挑选了部分leetcode中典型应用二分思想的题目。
1. 二分查找的总结
二分查找写法的核心在于缩小查找的边界，也就是不断地缩小查找范围，使得目标值在范围内。当查找范围为空集或找到了目标值时，就可以结束循环。如果懂得这个道理，二分查找写起来就简单多了。
1.1 普通的二分查找
最普通的二分查找，我们只要求它能找到目标元素或返回异常值（返回-1表示未查找到目标元素）就好。其基本思想非常好理解，就是利用数组的有序性来筛掉不必要进行查找的元素。
注意：
二分查找最重要一点就是边界条件的判断，在整个数组中进行查询时，可以使用\(lo<=hi\)的写法，其中hi的起始值为nums.length – 1。也可以采用\(lo<hi\)的的写法，其中hi的起始值为num.length：而且两种不同的边界条件lo和hi的变动也有所不同（详见如下代码）。
二分查找非递归实现：
public static int search(int[] nums, int target) {
return search(nums, target, 0, nums.length - 1);
}
// lo <= hi的写法，hi的初始值为nums.length - 1
public static int search(int[] nums, int target, int lo, int hi) {
while (lo <= hi) {
int mid = lo + (hi - lo) / 2; // 避免可能的溢出
if (nums[mid] < target)
lo = mid + 1; // 已经确定mid位置不可能是目标元素，将lo设置为mid的下一位
else if (nums[mid] > target)
hi = mid - 1; // 已经确定mid位置不可能是目标元素，将hi设置为mid的上一位
else
return mid; // 找到了就直接返回mid就好
}
return -1; // 没找到返回异常值
}
// lo < hi的写法，hi的初始值为nums.length - 1
public static int search2(int[] nums, int target, int lo, int hi) {
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] < target)
lo = mid + 1; // lo这侧为闭区间，写法与上面示例相同
else if (nums[mid] > target)
hi = mid; // hi这侧为开区间，写法与上面示例有区别！开区间这侧端点是取不到的，所以将hi设置为mid就好
else
return mid;
}
return -1;
}
二分查找递归实现：
public static int binarySearchRecur(int[] nums, int target, int low, int high) {
int mid = low + (high - low) / 2;
if (target > nums[mid])
return binarySearchRecur(nums, target, mid + 1, high);
else if (target < nums[mid])
return binarySearchRecur(nums, target, low, mid - 1);
else if (target == nums[mid])
return mid;
return -1;
}
注意：
-
为什么mid的计算方式不是$mid = \frac{(lo + hi)}{2} \(而是\)mid = lo + \frac{hi – lo}{2}$呢？
解答：毫无疑问的是，从数学上看两者是完全等价的。但是从数值计算的角度来看，若lo和hi都很大，lo直接与hi做和有溢出的可能，而第二种方式通过让hi与lo先做差，一定程度上避免了溢出的可能。
类似的有 mid * mid < target 可写为 mid < target < mid，也可以在一定程度上防止数字过大带来的溢出。
-
二分查找可以通过循环或递归的方式实现，但是递归方法的效率往往较低，在这里更推荐非递归写法。
一个困难：
上面实现的二分查找仅仅是找到数组中的一元素，可是有时候我们希望能获取更多信息。例如，当数组中可能存在很多个相同元素时，我们希望二分查找返回相同元素的最左边元素或最右边元素，这样方便我们提取出所有该重复元素。
有的同学可能会产生疑问，我只要通过二分查找找到目标元素，向左遍历或者向右遍历就好啦！总可以找到该元素最左侧或者最右侧位置嘛！可是这样在最坏情况的复杂度可能会上升至O(n)，例如数组中所有元素均相同时候。能不能将上面的二分查找代码稍作改进以在最坏情况下时间复杂度仍能保持在对数级别呢？
1.2 左边界二分查找
首先，普通的二分查找在找到目标元素位置后就直接返回了，但是若要查找左边界就不能让其直接返回，也就是在查找到目标元素后我们得想办法继续改变lo和hi指针，使得它们逐渐收缩至最左侧目标元素。这里由于个人习惯采取了lo和hi的选取设置为闭开区间的写法，也可以写为闭区间的形式。
public static int leftBound(int[] nums, int target) {
return leftBound(nums, target, 0, nums.length);
}
public static int leftBound(int[] nums, int target, int lo, int hi) {
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] < target)
lo = mid + 1;
// 其实下面两种情况都是一种解决方法，用一个else即可
// 但是为了逻辑清晰，这里暂时全部列出来
else if (nums[mid] > target)
hi = mid;
else
hi = mid; // 若找到了先不要返回，不断地将hi指针靠向lo指针方向
}
return nums[lo] == target ? lo : -1; // 可能找不到，不要忘记判断
}
1.3 右边界二分查找
如果你理解了左边界二分查找，右边界二分查找就十分简单了，思路都是相同的，只不过是在相等的情况下我们让lo指针靠近hi指针
public static int rightBound(int[] nums, int target) {
return rightBound(nums, target, 0, nums.length);
}
public static int rightBound(int[] nums, int target, int lo, int hi) {
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] < target)
lo = mid + 1;
else if (nums[mid] > target)
hi = mid;
else
lo = mid + 1; // 若找到了先不要返回，不断地将lo指针靠向hi指针方向
}
// 可以仔细推算一下，循环结束后lo与hi指向目标位置的下一个位置，所以下面是用lo - 1
// 不要忘记数组中可能不存在这个元素
return nums[lo - 1] == target ? lo - 1 : -1; // 仔细体会这个返回值
}
1.4 插入位置二分查找
如果有序数组中有目标元素值，我们直接返回其对应数组下标；若有序数组中没有目标元素值，我们返回目标值应该插入到的位置，也就是把这个目标值插入到此位置，新生成的数组是仍是有序的。
我们采用的形式十分类似于左边界二分查找，唯一的差别在于我们在return语句中不检查是否找到目标元素，直接返回lo对应的值即可。为了更好的理解这段代码为什么能够满足我们的要求，以下对lo指针的行为进行分析：
-
如果数组中存在目标元素:
显然此时代码的行为与左边界二分查找完全相同，会返回最左端的目标元素位置
-
如果数组中不存在目标元素：
lo指针与hi指针收缩到的位置只能有以下可能: 数组的最左端，数组的最右端、小于目标元素的最大元素（结合代码多看看），所以lo返回的位置就是目标元素应该插入到的位置。
public static int insertSearch(int[] nums, int target) {
return insertSearch(nums, target, 0, nums.length);
}
public static int insertSearch(int[] nums, int target, int lo, int hi) {
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] < target)
lo = mid + 1;
else if (nums[mid] > target)
hi = mid;
else
lo = mid + 1;
}
return lo;
}
2. 二分思想的应用（指Offer例题）
2.1 34. 在排序数组中查找元素的第一个和最后一个位置
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
进阶：
你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？
示例 1：
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
示例 2：
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]
示例 3：
输入：nums = [], target = 0
输出：[-1,-1]
提示：
0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums 是一个非递减数组
-109 <= target <= 109
2.1.1 题目分析
这道题看起来思路很清晰，我们只需要分别使用二分查找寻找左边界和右边界就好。
2.2.2 代码
class Solution {
public int[] searchRange(int[] nums, int target) {
if (nums.length == 0)
return new int[] {-1, -1};
int lo = 0, hi = nums.length;
// 寻找左边界
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] < target)
lo = mid + 1;
else
hi = mid;
}
// 这个地方需要仔细思考一下，如果查找左边界时发现了问题就直接返回异常值就好
if (lo == nums.length || nums[lo] != target)
return new int[] {-1, -1};
// 寻找右边界
int i = 0, j = nums.length;
while (i < j) {
int mid = i + (j - i) / 2;
if (nums[mid] > target)
j = mid;
else
i = mid + 1;
}
return new int[] {lo, i-1};
}
}
这是一个比较初级的写法，实际上可以通过一个函数同时查找左边界和右边界，可以查看对应题目的官方题解。
2.2 69. x 的平方根
由于返回类型是整数，结果只保留整数部分，小数部分将被 舍去 。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
示例 1：
输入：x = 4
输出：2
示例 2：
输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
提示：\(0 <= x <= 2^{31} – 1\)
2.2.1 题目分析
只要读完题目就知道本题实际上是要我们求出x平方根的整数部分，也就是求一个整数k，满足k的平方小于x且\(0<x – k^2<1\)。
如果按照暴力的解法来看，我们只需要从1开始遍历整数k，直到找到合适的k为止（也就是当此时的k平方大于x时，返回k-1），这样的时间复杂度为O(n)。
其实在上面的过程中我们使用了顺序查找，而且查找的序列还是一个有序的序列，我们可以使用二分查找来降低时间复杂度。(为什么本题与二分查找联系在一起）。
2.2.2 代码
class Solution {
public int mySqrt(int x) {
// 设置一个ans来记录当前的一个合适的mid值
int l = 0, r = x, ans = -1;
while (l <= r) { // 当然你可以选择 l < r的写法，但是本题x的取值范围可达到整数最大值，这么做会不太方便
int mid = l + (r - l) / 2;
// 由于mid的范围很大，不转换则会溢出
// 可以使用我们上面提到的方法来防止溢出，但是需要额外设置一些特殊值检查来防止特殊值（0，1）
if ((long)mid * mid <= x) {
ans = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
// 当循环结束时，ans一定与较小的lo或者hi相等，要注意理解
// 这个ans是我们妥协出来的产物，如果x范围不会达到int类型最大值，采用l < r则不需要ans了
return ans;
}
}
这道题实际上还有很多有趣的解法：例如袖珍计算器法、牛顿迭代法，但由于本专题是在讨论二分查找问题，故不再介绍这些方法，详见对应官方解析页面。
2.3 367. 有效的完全平方数
给定一个 正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false 。
进阶：不要 使用任何内置的库函数，如 sqrt 。
示例 1：
输入：num = 16
输出：true
示例 2：
输入：num = 14
输出：false
2.3.1 题目分析
检验完全平方数实际上就是从1到num这个整数序列中查找是否存在一个数k，其满足k的平方等于num，如果不存在这样的k则意味着num不是完全平方数。所以可以用二分的思想来寻找这个整数k。
2.3.2 代码
class Solution {
public boolean isPerfectSquare(int num) {
int lo = 1, hi = num;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
long val = (long)mid * mid; // 注意这个显示的类型转换，尤其是mid前面的那个
if (val > num)
hi = mid - 1;
else if (val < num)
lo = mid + 1;
else
return true; // 找到k就直接返回true
}
return false; // 如果循环都结束了还没找到只能说明这样的k是不存在的，所以返回false
}
}
2.4 153. 寻找旋转排序数组中的最小值与154. 寻找旋转排序数组中的最小值 II
已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：
若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]
注意，数组 [a[0], a[1], a[2], …, a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], …, a[n-2]] 。
给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
示例 1：
输入：nums = [3,4,5,1,2]
输出：1
解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。
示例 2：
输入：nums = [4,5,6,7,0,1,2]
输出：0
解释：原数组为 [0,1,2,4,5,6,7] ，旋转 4 次得到输入数组。
示例 3：
输入：nums = [11,13,15,17]
输出：11
解释：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。
提示：
n == nums.length
1 <= n <= 5000
-5000 <= nums[i] <= 5000
nums 原来是一个升序排序的数组，并进行了 1 至 n 次旋转
2.4.1 题目分析
数组的一次旋转其实就是将最后一位元素提到最前面来，旋转n次之后可能会出现这样的结果：数组被分为两个有序部分，我们不妨分别称之为左有序数组、右有序数组。当左有序数组、右有序数组长度不为0时，左有序数组元素是要大于等于右有序数组的元素的；当左有序数组为0时，最左端位置就是最小元素；当右有序数组为0时，最右端元素为最小元素。
这样一道题看起来与二分查找有什么关联呢？而且这个数组甚至不是完全有序的！下面来分析一下为什么二分思想在本题是可以应用。
可以利用左子数组与右子数组特性——左子树组与右子数组均递增且左子数组元素大于等于右子数组元素
我们设置两个指针lo和hi，分别指向数组头和尾，比较mid = (lo + hi) / 2，比较nums[mid]与nums[hi]的值
- 若nums[mid] < nums[hi]，说明mid指向右子数组元素，将lo指针挪至mid处（mid指向的位置本身就可以为最小元素）
- 若nums[mid] > nums[hi]，说明mid指向左子数组元素，将lo指针挪至mid + 1处（mid所指向位置不可能是最小元素）
-
如果nums[mid] == nums[hi]，遇到重复值情形，此时可以将hi — (如果考虑这个情况可能会出错)
注意：
如果不考虑重复值带来的影响，可能会出现死循环或者无法找到正确值的情况（取决于你的代码实现）。如何合理处理以上情况呢？
当左子数组和右子数组均存在时（当左子数组不存在时，相当于数组是升序情况，二分查找的思想很显然可以应用），左子数组元素大于等于右子数组且两者均升序。如果mid所指向值等于hi指向值，可以将断定删除hi所指向的值并不影响最终结果的查找。删除掉hi所指向的元素值，不会使最小值从数组中被删去（即使被删除的元素是最小值，那么数组中仍存在该最小值）。要好好理解！
2.4.2 代码
class Solution {
public int findMin(int[] nums) {
int lo = 0, hi = nums.length - 1;
int mid;
while (lo < hi) {
mid = lo + (hi - lo) / 2;
if (nums[mid] > nums[hi])
lo = mid + 1;
else if (nums[mid] < nums[hi])
hi = mid;
else
hi -= 1;
}
return nums[lo];
}
}
2.5 剑指 Offer 53 – II. 0～n-1中缺失的数字
一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
示例 1:输入: [0,1,3]
输出: 2
示例 2:输入: [0,1,2,3,4,5,6,7,9]
输出: 8
限制：1 <= 数组长度 <= 10000
2.5.1 题目分析
由于本题还是一个有序数组，应该首先想想能否使用二分查找或利用类似的思想去解决问题。
首先，长度为n-1的数组取值为0到n，仅缺失一个元素，而题目要我们查找出这个缺失值。可能看起来有些奇怪是不是？其实这个形式与之前我们写过的查找插入位置的二分查找是类似的。
如果数组长度是n且升序排列，那么实际上数组元素与其下标是相等的，但是缺失了一个元素之后，缺失元素右侧全部元素数组下标均较少1，也就是在缺失元素前的元素值仍等于数组下标。数组被分为了两个部分，我们要做的也就是查找却缺失元素右侧第一个元素，或者说右侧数组的开头元素。
2.5.2 代码
// 二分搜索
class Solution {
public int missingNumber(int[] nums) {
int mid;
int lo = 0, hi = nums.length;
while (lo < hi) {
mid = lo + (hi - lo) / 2;
if (nums[mid] == mid) // 注意这个搜索条件
lo = mid + 1;
else
hi = mid;
}
return lo;
}
}
