二分查找 红蓝染色法
核心概念：
- 将数组染成红蓝两色，红色是一个条件，蓝色则是另一个条件。比如在二分查找中，红色表示小于 target， 蓝色则表示大于等于 target。
- 中止时指针状态（以开区间为例）：
- 此时 l + 1 = r
- l及左边都是红色（小于 target）
- r及右边都是蓝色（大于等于 target）
例如：关于开区间二分，如何理解 −1 和 n 这两个下标？可以假设 nums[−1]=−∞ 以及 nums[n]=∞，此时 nums 仍然是有序的。在这种情况下，nums[−1]<target，所以 −1 是红色；nums[n]≥target，所以 n 是蓝色。
问：为什么要写 left + (right - left) / 2 ？
答：在面试或者实际场景中，你不一定知道输入的数组有多长，万一数组长度达到 int 最大值，left + right 可能会发生加法溢出。当然，如果只看本题的数据范围，写 (left + right) / 2 也可以。对于 Python 来说，由于没有溢出这个概念，所以可以直接相加。
闭区间写法
class Solution {
// lower_bound 返回最小的满足 nums[i] >= target 的下标 i
// 如果数组为空，或者所有数都 < target，则返回 nums.size()
// 要求 nums 是非递减的，即 nums[i] <= nums[i + 1]
int lower_bound(vector<int>& nums, int target) {
int left = 0, right = (int) nums.size() - 1; // 闭区间 [left, right]
while (left <= right) { // 区间不为空
// 循环不变量：
// nums[left-1] < target
// nums[right+1] >= target
int mid = left + (right - left) / 2;
if (nums[mid] >= target) {
right = mid - 1; // 范围缩小到 [left, mid-1]
} else {
left = mid + 1; // 范围缩小到 [mid+1, right]
}
}
// 循环结束后 left = right+1
// 此时 nums[left-1] < target 而 nums[left] = nums[right+1] >= target
// 所以 left 就是第一个 >= target 的元素下标
return left;
}
public:
vector<int> searchRange(vector<int>& nums, int target) {
int start = lower_bound(nums, target);
if (start == nums.size() || nums[start] != target) {
return {-1, -1}; // nums 中没有 target
}
// 如果 start 存在，那么 end 必定存在
int end = lower_bound(nums, target + 1) - 1;
return {start, end};
}
};
左闭右开区间写法
class Solution {
// lower_bound 返回最小的满足 nums[i] >= target 的下标 i
// 如果数组为空，或者所有数都 < target，则返回 nums.size()
// 要求 nums 是非递减的，即 nums[i] <= nums[i + 1]
int lower_bound(vector<int>& nums, int target) {
int left = 0, right = nums.size(); // 左闭右开区间 [left, right)
while (left < right) { // 区间不为空
// 循环不变量：
// nums[left-1] < target
// nums[right] >= target
int mid = left + (right - left) / 2;
if (nums[mid] >= target) {
right = mid; // 范围缩小到 [left, mid)
} else {
left = mid + 1; // 范围缩小到 [mid+1, right)
}
}
// 循环结束后 left = right
// 此时 nums[left-1] < target 而 nums[left] = nums[right] >= target
// 所以 left 就是第一个 >= target 的元素下标
return left;
}
public:
vector<int> searchRange(vector<int>& nums, int target) {
int start = lower_bound(nums, target);
if (start == nums.size() || nums[start] != target) {
return {-1, -1}; // nums 中没有 target
}
// 如果 start 存在，那么 end 必定存在
int end = lower_bound(nums, target + 1) - 1;
return {start, end};
}
};
开区间写法
class Solution {
// lower_bound 返回最小的满足 nums[i] >= target 的下标 i
// 如果数组为空，或者所有数都 < target，则返回 nums.size()
// 要求 nums 是非递减的，即 nums[i] <= nums[i + 1]
int lower_bound(vector<int>& nums, int target) {
int left = -1, right = nums.size(); // 开区间 (left, right)
while (left + 1 < right) { // 区间不为空
// 循环不变量：
// nums[left] < target
// nums[right] >= target
int mid = left + (right - left) / 2;
if (nums[mid] >= target) {
right = mid; // 范围缩小到 (left, mid)
} else {
left = mid; // 范围缩小到 (mid, right)
}
}
// 循环结束后 left+1 = right
// 此时 nums[left] < target 而 nums[right] >= target
// 所以 right 就是第一个 >= target 的元素下标
return right;
}
public:
vector<int> searchRange(vector<int>& nums, int target) {
int start = lower_bound(nums, target);
if (start == nums.size() || nums[start] != target) {
return {-1, -1}; // nums 中没有 target
}
// 如果 start 存在，那么 end 必定存在
int end = lower_bound(nums, target + 1) - 1;
return {start, end};
}
};
class Solution {
// lower_bound 返回最小的满足 nums[i] >= target 的下标 i
// 如果数组为空，或者所有数都 < target，则返回 nums.size()
// 要求 nums 是非递减的，即 nums[i] <= nums[i + 1]
int lower_bound(vector<int>& nums, int target) {
int left = -1, right = nums.size(); // 开区间 (left, right)
while (left + 1 < right) { // 区间不为空
// 循环不变量：
// nums[left] < target
// nums[right] >= target
int mid = left + (right - left) / 2;
(nums[mid] >= target ? right : left) = mid; // 注：只有开区间二分可以这样写
}
// 循环结束后 left+1 = right
// 此时 nums[left] < target 而 nums[right] >= target
// 所以 right 就是第一个 >= target 的元素下标
return right;
}
public:
vector<int> searchRange(vector<int>& nums, int target) {
int start = lower_bound(nums, target);
if (start == nums.size() || nums[start] != target) {
return {-1, -1}; // nums 中没有 target
}
// 如果 start 存在，那么 end 必定存在
int end = lower_bound(nums, target + 1) - 1;
return {start, end};
}
};
库函数写法
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
int start = ranges::lower_bound(nums, target) - nums.begin();
if (start == nums.size() || nums[start] != target) {
return {-1, -1};
}
int end = ranges::upper_bound(nums, target) - nums.begin() - 1;
return {start, end};
}
};
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
auto [start, end] = ranges::equal_range(nums, target);
if (start == end) {
return {-1, -1};
}
return {(int) (start - nums.begin()), (int) (end - nums.begin() - 1)};
}
};
题解链接：
作者：灵茶山艾府
链接：https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/solutions/1980196/er-fen-cha-zhao-zong-shi-xie-bu-dui-yi-g-t9l9/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。