二分总结（LeetCode Hot 100 的二分题）
二分就两种情况：一种是找目标值，另一种是找边界。
循环的跳出条件也因此不同：
- 找目标值：
while (l <= r)，因为l == r的情况也需要被考虑到，那是最后一个元素。 - 找边界值：
while (l < r)，因为最终l和r会重合在边界上。
一、查找目标值
这种最简单，无非就是定义 l、r，然后根据 mid 的值来移动指针。
1. 搜索二维矩阵
给你一个满足下述两条属性的
m x n整数矩阵：
- 每行中的整数从左到右按非严格递增顺序排列。
- 每行的第一个整数大于前一行的最后一个整数。
给你一个整数
target，如果target在矩阵中，返回true；否则，返回false。
示例 1：
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true
示例 2：
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出：false
这题比较简单没啥说的，只要把二维矩阵的坐标 (x, y) 和一维的索引 mid 对应起来就行。
代码：
Java
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length;
int n = matrix[0].length;
int l = 0;
int r = n * m - 1;
while (l <= r) {
int mid = l + r >> 1;
int x = mid / n; // 通过整除计算行号
int y = mid % n; // 通过取余计算列号
if (matrix[x][y] == target)
return true;
else if (matrix[x][y] > target)
r = mid - 1;
else
l = mid + 1;
}
return false;
}
}
2. 搜索旋转排序数组
整数数组
nums按升序排列，数组中的值 互不相同 。在传递给函数之前，
nums在预先未知的某个下标k（0 <= k < nums.length）上进行了 向左旋转，使数组变为[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]。给你 旋转后 的数组
nums和一个整数target，如果nums中存在这个目标值target，则返回它的下标，否则返回-1。你必须设计一个时间复杂度为
O(log n)的算法解决此问题。
示例 1：
输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4
示例 2：
输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1
这道题唯一需要注意的地方就在于，需要找到那个旋转点，然后把数组分成左右两个有序的区域，分别进行二分查找。也比较简单。
代码：
Java
class Solution {
public int search(int[] nums, int target) {
int n = nums.length - 1;
int idx = 0;
// 找旋转点 (注意：这个找法是 O(n)，不满足题目 O(log n) 的要求，但思路是这样)
while (idx < n && nums[idx] < nums[idx + 1])
idx++;
// 在左半边有序区域二分
int l = 0;
int r = idx;
while (l <= r) {
int m = l + r >> 1;
if (nums[m] == target)
return m;
else if (nums[m] > target)
r = m - 1;
else
l = m + 1;
}
// 在右半边有序区域二分
l = idx + 1;
r = n;
while (l <= r) {
int m = l + r >> 1;
if (nums[m] == target)
return m;
else if (nums[m] > target)
r = m - 1;
else
l = m + 1;
}
return -1;
}
}
二、查找边界
这种问题稍微复杂一点，关键在于 check() 条件的判断以及 mid 的取整方式，先上两个常用的模版。
模版1：寻找左边界 (Leftmost Boundary)
目的是在一个区间内找到满足某个条件的第一个元素。
Java
while (l < r) {
int m = l + r >> 1; // or l + (r - l) / 2
if(check(m)) r = m; // 如果m满足条件，那它可能是左边界，也可能在它左边还有，所以收缩右边界
else l = m + 1;
}
return l;
模版2：寻找右边界 (Rightmost Boundary)
目的是在一个区间内找到满足某个条件的最后一个元素。
Java
while (l < r) {
int m = l + r + 1 >> 1; // or l + (r - l + 1) / 2，必须向上取整，否则可能死循环
if(check(m)) l = m; // 如果m满足条件，那它可能是右边界，也可能在它右边还有，所以收缩左边界
else r = m - 1;
}
return l;
3. 搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为
O(log n)的算法。
示例 1:
输入: nums = [1,3,5,6], target = 5
输出: 2
示例 2:
输入: nums = [1,3,5,6], target = 2
输出: 1
这道题就是典型的找边界，我们需要找的是第一个大于等于 target 的数的位置，直接套用寻找左边界的模版就行。
代码：
Java
class Solution {
public int searchInsert(int[] nums, int target) {
int n = nums.length;
int l = 0;
int r = n; // 注意 r 的初始值是 n，因为可能插入到最后
while (l < r) {
int m = l + r >> 1;
if (nums[m] >= target) // 找到一个大于等于它的数，它可能是最终结果，也可能左边还有
r = m;
else
l = m + 1;
}
return l;
}
}
4. 在排序数组中查找元素的第一个和最后一个位置
给你一个按照非递减顺序排列的整数数组
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]
这道题就是上面两个模版的完美结合。
- 找开始位置：就是找
target的左边界，套模版1。 - 找结束位置：就是找
target的右边界，套模版2。
代码：
Java
class Solution {
public int[] searchRange(int[] nums, int target) {
int[] res = { -1, -1 };
if (nums.length == 0)
return res;
int l = 0;
int r = nums.length - 1;
// 寻找左边界
while (l < r) {
int m = l + r >> 1;
if (nums[m] >= target)
r = m;
else
l = m + 1;
}
// 如果找不到 target，直接返回
if (nums[l] != target)
return res;
res[0] = l;
// 重置 r，寻找右边界
// l 不用重置，因为右边界肯定在 l 的右边或就是 l
r = nums.length - 1;
while (l < r) {
int m = l + r + 1 >> 1; // 向上取整
if (nums[m] <= target)
l = m;
else
r = m - 1;
}
res[1] = l;
return res;
}
}
5. 寻找旋转排序数组中的最小值
已知一个长度为
n的数组，预先按照升序排列，经由1到n次 旋转 后，得到输入数组。给你一个元素值 互不相同 的数组
nums，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。你必须设计一个时间复杂度为
O(log n)的算法解决此问题。
示例 1：
输入：nums = [3,4,5,1,2]
输出：1
示例 2：
输入：nums = [4,5,6,7,0,1,2]
输出：0
这道题的关键点在于怎么通过 mid 来判断最小值在哪一侧。对于中点 m，用 [4,5,6,7,0,1,2] 举例：
- 如果
m落在7，那么它的下一个点0就是最小值，也就是找到了旋转点。 - 如果
m落在左半边递增区域（如4,5,6），说明nums[m] >= nums[l]，旋转点（最小值）肯定在右边，所以l = m + 1。 - 如果
m落在右半边递增区域（如0,1,2），说明nums[m] < nums[l]，旋转点（最小值）就是m或者在m的左边，所以r = m(或者r = m - 1，取决于具体逻辑)。
代码：
Java
class Solution {
public int findMin(int[] nums) {
int n = nums.length;
// 如果数组没有旋转
if (nums[0] <= nums[n - 1]) {
return nums[0];
}
int l = 0;
int r = n - 1;
while (l <= r) {
int m = l + r >> 1;
// 找到了旋转点，它的下一个元素就是最小值
if (m < n - 1 && nums[m] > nums[m + 1]) {
return nums[m + 1];
}
// mid 的前一个元素是旋转点
if (m > 0 && nums[m] < nums[m - 1]) {
return nums[m];
}
// 如果 mid 在左半部分（值较大的一侧），那最小值在右侧
if (nums[m] >= nums[0]) {
l = m + 1;
}
// 如果 mid 在右半部分（值较小的一侧），那最小值在左侧
else {
r = m - 1;
}
}
return -1; // 根据题目条件，不会执行到这里
}
}
6. 寻找两个正序数组的中位数
给定两个大小分别为
m和n的正序（从小到大）数组nums1和nums2。请你找出并返回这两个正序数组的 中位数 。算法的时间复杂度应该为
O(log (m+n))。
示例 1：
输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2
示例 2：
输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
这道题最简单的解法是合并两个数组，但时间复杂度会达到 O(m+n)。要做到 O(log(m+n)) 只能用二分。这道题自己想确实很难想出来，思路确实很巧妙：核心是在较短的那个数组上进行二分，找到一个完美的分割点，这个分割点能将两个数组划分成四个部分，满足左边所有元素都小于等于右边所有元素，并且左边元素个数和右边元素个数相等（或差一）。
代码：
Java
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
// 确保对较短的数组进行二分，以减少查找次数
if (nums1.length > nums2.length) {
int[] temp = nums1;
nums1 = nums2;
nums2 = temp;
}
int m = nums1.length;
int n = nums2.length;
int l = 0;
int r = m; // 在 nums1 上进行二分查找
while (l <= r) {
// i 是 nums1 的分割点，j 是 nums2 的分割点
int i = (l + r) / 2;
int j = (m + n + 1) / 2 - i;
// 获取分割线左右两侧的四个关键值
int nums1LeftMax = (i == 0) ? Integer.MIN_VALUE : nums1[i - 1];
int nums1RightMin = (i == m) ? Integer.MAX_VALUE : nums1[i];
int nums2LeftMax = (j == 0) ? Integer.MIN_VALUE : nums2[j - 1];
int nums2RightMin = (j == n) ? Integer.MAX_VALUE : nums2[j];
// 检查是否是完美分割
if (nums1LeftMax <= nums2RightMin && nums2LeftMax <= nums1RightMin) {
// 如果是奇数个元素，中位数是左半部分的最大值
if ((m + n) % 2 == 1) {
return Math.max(nums1LeftMax, nums2LeftMax);
} else {
// 如果是偶数个元素，中位数是左半部分最大值和右半部分最小值的平均
return (Math.max(nums1LeftMax, nums2LeftMax) + Math.min(nums1RightMin, nums2RightMin)) / 2.0;
}
} else if (nums1LeftMax > nums2RightMin) {
// nums1 的左半部分太大了，需要将分割线 i 左移
r = i - 1;
} else {
// nums1 的左半部分太小了，需要将分割线 i 右移
l = i + 1;
}
}
// 根据题目条件，不会执行到这里
throw new IllegalArgumentException("Input arrays are not sorted.");
}
}