二分查找边界写法总结
三种区间写法
- 闭区间：询问答案是否在
[left, right]。循环结束时left > right（即right + 1 == left），返回left。 - 左闭右开：询问答案是否在
[left, right)。结束时left == right，返回left（或right）。 - 开区间：询问答案是否在
(left, right)。结束时left + 1 == right，返回right。
while 条件
本质是“区间不为空”：
- 闭区间：
left <= right - 左闭右开：
left < right - 开区间：
left + 1 < right
返回 left 还是 right
程序退出循环时，left/right 的关系是固定的。要返回哪个值，只需分析循环最后一步执行后两个指针的状态。
也可以通过“循环开始前的不变量”来推导。
==思考：在闭区间中，left 的含义是什么==
- 设
left = 0，0位置最初是未知的，因此left表示的是：[0, ..., left-1]都小于target。 - 对称地，
right表示：[right+1, ..., end]都大于等于target。 - 因此更新
left时必须保证left仍然指向未知区域，即left = mid + 1（mid已知）。 - 在左闭右开写法中，
left从0开始，right从n开始（n是已知边界），因此右侧更新为right = mid。
if 条件建议只写成 nums[mid] < target 和 nums[mid] >= target 两类，避免混入 <= 导致边界混乱。
class Solution {
public int searchInsert(int[] nums, int target) {
return lowerBound(nums, target); // 选择其中一种写法即可
}
// lowerBound 返回最小的满足 nums[i] >= target 的 i
// 如果数组为空，或者所有数都 < target，则返回 nums.length
// 要求 nums 是非递减的，即 nums[i] <= nums[i + 1]
// 闭区间写法
private int lowerBound(int[] nums, int target) {
int left = 0;
int right = nums.length - 1; // 闭区间 [left, right]
while (left <= right) { // 区间不为空
// 循环不变量：
// nums[left-1] < target
// nums[right+1] >= target
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1; // 范围缩小到 [mid+1, right]
} else {
right = mid - 1; // 范围缩小到 [left, mid-1]
}
}
return left;
}
// 左闭右开区间写法
private int lowerBound2(int[] nums, int target) {
int left = 0;
int right = nums.length; // 左闭右开区间 [left, right)
while (left < right) { // 区间不为空
// 循环不变量：
// nums[left-1] < target
// nums[right] >= target
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1; // 范围缩小到 [mid+1, right)
} else {
right = mid; // 范围缩小到 [left, mid)
}
}
return left; // 或者 right
}
// 开区间写法
private int lowerBound3(int[] nums, int target) {
int left = -1;
int right = nums.length; // 开区间 (left, right)
while (left + 1 < right) { // 区间不为空
// 循环不变量：
// nums[left] < target
// nums[right] >= target
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid; // 范围缩小到 (mid, right)
} else {
right = mid; // 范围缩小到 (left, mid)
}
}
return right;
}
}
颜色定义
-
目标是判断
mid的颜色，而颜色由mid与target的相对位置决定。 -
二分查找（递增数组）：
-
nums[mid]是target或target右侧，染成蓝色；其余染成红色。
找第一个满足 和最后一个满足
- 第一个满足：常用左闭右开。
- 最后一个满足：常用左开右闭。
if (condition)分支中通常只做l = mid或r = mid，而不是mid ± 1。condition的本质是下标关系，不是元素值关系。 在有序数组中，两者才会建立映射。- 例如“查找第一个
>= target的下标”，condition可理解为“答案在mid左侧（含mid）”。
// 返回第一个满足 condition 的下标，不存在则返回 n
// fffttt
static int firstTrue(int n) {
int l = 0, r = n; // [l, r)
while (l < r) {
int mid = l + (r - l) / 2;
if (condition(mid)) { //**target在mid左侧及mid**
r = mid; // mid 可能是答案，收缩右边界
} else {
l = mid + 1; // mid 不满足，排除
}
}
return l;
}
- 最后一个满足：
condition可理解为target.index >= mid。 - 例如“最后一个
<= 10”，此时mid满足条件就继续向右找。
// 返回最后一个满足 condition 的下标，不存在返回 -1
// tttffff
static int lastTrue(int n) {
int l = -1, r = n - 1; // (l, r]
while (l < r) {
int mid = l + (r - l + 1) / 2; // 注意 +1，向右取中点
if (condition(mid)) { // **target在mid右侧及mid**
l = mid; // mid 满足，保留，向右找
} else {
r = mid - 1; // mid 不满足，丢掉右半边
}
}
return l;
}
中位数
- 思路是找最后一个满足
left1 <= right2的切分点。 - 二分范围是
[0, m]，写成左开右闭可设l = -1, r = m，并在if (condition)中执行l = mid。
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;
// m+n : 奇数: m+n+1/2 , 偶数 m+n/2 合并 m+n+1/2个,
int totalCount = (m+n+1)/2;
// left1 是第一个数组左边最后一个, right1是第一个数组右边第一个, left2是第二个数组左边最后一个
// 现在进行二分查找, 针对第一个数组取多少个数进行二分查找, 范围是 [0,m], 我们发现 left1<=right2 , 一开始满足渐渐不满足了,
// 因此我们要找最后一个满足的情况 因此 左开右闭 (-1,m]
int left = -1;
int right = m;
while (left<right) {
int i = left+(right-left+1)/2;
int j = totalCount - i;
int left1 = i==0?Integer.MIN_VALUE:nums1[0+i-1];
int right2 =j>=n?Integer.MAX_VALUE: nums2[j];
if (left1<=right2) {
left = i;
}else{
right = i-1;
}
}
// left==right
int i = left;
int j = totalCount-i;
int left1 = i==0?Integer.MIN_VALUE:nums1[i-1];
int right1 = i>=m?Integer.MAX_VALUE:nums1[i];
int left2 = j==0?Integer.MIN_VALUE:nums2[j-1];
int right2 = j>=n?Integer.MAX_VALUE:nums2[j];
if ((m+n)%2==0) {
return (Math.max(left1, left2)+Math.min(right1, right2))/2.0;
}else{
return Math.max(left1,left2);
}
}
}