【基础算法】一文详解二分及其重要性质
二分
今天通过几道 LC 上最热门的「二分」题目，带大家学习何为二分，以及二分对应的几类模板有和区别。
在掌握模板的基础上，带大家进一步的了解二分的本质，算法新手往往对觉得使用二分的充要条件是给定数据具有单调性，实则不然。
153. 寻找旋转排序数组中的最小值
已知一个长度为 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 ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
示例 1：
输入：nums = [3,4,5,1,2]
输出：1
解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。
提示：
- n == nums.length
- 1 <= n <= 5000
- -5000 <= nums[i] <= 5000
- nums 中的所有整数 互不相同
- nums 原来是一个升序排序的数组，并进行了 1 至 n 次旋转
二分查找
今天这道题和昨天的 81. 搜索旋转排序数组 II 相比，有了限制条件「所有整数互不相同」。
因此我们不需要进行「恢复二段性」的预处理，是可以做到严格 O(logn)O(log{n})O(logn) 的复杂度。
我们仍然从「二分」的本质「二段性」进行出发分析：
经过旋转的数组，显然前半段满足 >= nums[0]，而后半段不满足 >= nums[0]。我们可以以此作为依据，通过「二分」找到旋转点。然后通过旋转点找到全局最小值即可。
代码：
class Solution {
public int findMin(int[] nums) {
int n = nums.length;
int l = 0, r = n - 1;
while (l < r) {
int mid = l + r + 1 >> 1;
if (nums[mid] >= nums[0]) {
l = mid;
} else {
r = mid - 1;
}
}
return r + 1 < n ? nums[r + 1] : nums[0];
}
}
- 时间复杂度：O(logn)O(\log{n})O(logn)
- 空间复杂度：O(1)O(1)O(1)
33. 搜索旋转排序数组
整数数组 nums 按升序排列，数组中的值 互不相同 。
在传递给函数之前，nums 在预先未知的某个下标 k （0 <= k < nums.length）上进行了旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。
例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
给你旋转后的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
示例 1：
输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4
示例 2：
输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1
示例 3：
输入：nums = [1], target = 0
输出：-1
提示：
- 1<=nums.length<=50001 <= nums.length <= 50001<=nums.length<=5000
- −104<=nums[i]<=104-10^4 <= nums[i] <= 10^4−104<=nums[i]<=104
nums中的每个值都 独一无二- 题目数据保证
nums在预先未知的某个下标上进行了旋转 - −104<=target<=104-10^4 <= target <= 10^4−104<=target<=104
进阶：你可以设计一个时间复杂度为 O(logn)O(\log{n})O(logn) 的解决方案吗？
朴素解法
但凡是从有序序列中找某个数，我们第一反应应该是「二分」。
这道题是一个原本有序的数组在某个点上进行了旋转，其实就是将原本一段升序的数组分为了两段。
我们可以先找到旋转点 idx，然后对 idx 前后进行「二分」。
代码：
class Solution {
public int search(int[] nums, int target) {
int n = nums.length;
int idx = 0;
for (int i = 0; i < n - 1; i++) {
if (nums[i] > nums[i + 1]) {
idx = i;
break;
}
}
int ans = find(nums, 0, idx, target);
if (ans != -1) return ans;
if (idx + 1 < n) ans = find(nums, idx + 1, n - 1, target);
return ans;
}
int find(int[] nums, int l, int r, int target) {
while (l < r) {
int mid = l + r >> 1;
if (nums[mid] >= target) {
r = mid;
} else {
l = mid + 1;
}
}
return nums[l] == target ? l : -1;
}
}
- 时间复杂度：先对数组进行一次遍历，找到
idx，复杂度为 O(n)O(n)O(n)，对idx前后进行二分查找，复杂度为 O(logn)O(\log{n})O(logn)。整体为 O(n)O(n)O(n) - 空间复杂度：O(1)O(1)O(1)
二分解法
不难发现，虽然在朴素解法中我们应用了「二分」查找。
但理论复杂度为 O(n)O(n)O(n)，实际复杂度也远达不到 O(logn)O(\log{n})O(logn)，执行效率取决于旋转点 idx 所在数组的下标位置。
那么我们如何实现 O(logn)O(\log{n})O(logn) 的解法呢？
这道题其实是要我们明确「二分」的本质是什么。
「二分」不是单纯指从有序数组中快速找某个数，这只是「二分」的一个应用。
「二分」的本质是两段性，并非单调性。只要一段满足某个性质，另外一段不满足某个性质，就可以用「二分」。
经过旋转的数组，显然前半段满足 >= nums[0]，而后半段不满足 >= nums[0]。我们可以以此作为依据，通过「二分」找到旋转点。
找到旋转点之后，再通过比较 target 和 nums[0] 的大小，确定 target 落在旋转点的左边还是右边。
代码：
class Solution {
public int search(int[] nums, int target) {
int n = nums.length;
if (n == 0) return -1;
if (n == 1) return nums[0] == target ? 0 : -1;
// 第一次「二分」：从中间开始找，找到满足 >=nums[0] 的分割点（旋转点）
int l = 0, r = n - 1;
while (l < r) {
int mid = l + r + 1 >> 1;
if (nums[mid] >= nums[0]) {
l = mid;
} else {
r = mid - 1;
}
}
// 第二次「二分」：通过和 nums[0] 进行比较，得知 target 是在旋转点的左边还是右边
if (target >= nums[0]) {
l = 0;
} else {
l = l + 1;
r = n - 1;
}
while (l < r) {
int mid = l + r >> 1;
if (nums[mid] >= target) {
r = mid;
} else {
l = mid + 1;
}
}
return nums[r] == target ? r : -1;
}
}
- 时间复杂度：O(logn)O(\log{n})O(logn)
- 空间复杂度：O(1)O(1)O(1)
34. 在排序数组中查找元素的第一个和最后一个位置
给定一个按照升序排列的整数数组 nums，和一个目标值 target。
找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [−1,−1][-1, -1][−1,−1]。
进阶：
- 你可以设计并实现时间复杂度为 O(logn)O(\log{n})O(logn) 的算法解决此问题吗？
示例 1：
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
提示：
- 0<=nums.length<=1050 <= nums.length <= 10^50<=nums.length<=105
- −109 <=nums[i] <=109-10^9 <= nums[i] <= 10^9−109 <=nums[i] <=109
nums是一个非递减数组- −109 <=target <=109-10^9 <= target <= 10^9−109 <=target <=109
二分解法
这是一道「二分查找」的裸题。
「二分」有一个比较容易混淆的点是：当需要找目标值第一次出现的下标时，条件应该写成 nums[mid] >= target 还是 nums[mid] <= target。
其实有一个很好理解的方法：
由于二分是从中间开始找起的，所以找的必然是条件区间中靠近中心的的边界值。
文字不好理解，我们结合图片来看：
代码：
class Solution {
public int[] searchRange(int[] nums, int t) {
int[] ans = new int[]{-1, -1};
int n = nums.length;
if (n == 0) return ans;
int l = 0, r = n - 1;
while (l < r) {
int mid = l + r >> 1;
if (nums[mid] >= t) r = mid;
else l = mid + 1;
}
if (nums[r] != t) return ans;
ans[0] = r;
l = 0; r = n - 1;
while (l < r) {
int mid = l + r + 1 >> 1;
if (nums[mid] <= t) l = mid;
else r = mid - 1;
}
ans[1] = r;
return ans;
}
}
- 时间复杂度：O(logn)O(\log{n})O(logn)
- 空间复杂度：O(1)O(1)O(1)
35. 搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。
如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
示例 1:
输入: [1,3,5,6], 5
输出: 2
朴素做法
一个朴素的做法，从前往后进行处理，直到遇到符合条件的位置。
代码：
class Solution {
public int searchInsert(int[] nums, int t) {
for (int i = 0; i < nums.length; i++) {
if (nums[i] == t || nums[i] > t) return i;
}
return nums.length;
}
}
- 时间复杂度：O(n)O(n)O(n)
- 空间复杂度：O(1)O(1)O(1)
二分解法
利用数组本身有序，我们可以通过二分找插入位置。
具体的，通过二分找到符合 nums[mid] >= t 的分割点。注意二分完后需要再次检查是否位置是否符合条件，如果不符合，代表插入元素应该被添加到数组结尾。
代码：
class Solution {
public int searchInsert(int[] nums, int t) {
int n = nums.length;
int l = 0, r = n - 1;
while (l < r) {
int mid = l + r >> 1;
if (nums[mid] >= t) {
r = mid;
} else {
l = mid + 1;
}
}
return nums[r] >= t ? r : r + 1;
}
}
- 时间复杂度：O(logn)O(\log{n})O(logn)
- 空间复杂度：O(1)O(1)O(1)
总结
综上，「二分」的本质是两段性，并非单调性。只要一段满足某个性质，另外一段不满足某个性质，就可以用「二分」。
同时，在考虑使用何种二分模板时，切忌不要硬套模板，多从「二分的是什么内容」的角度进行出发思考。
转载自:https://juejin.cn/post/7241951082792845369