二分法如何应用于解决搜索问题？
摘要：概述 二分查找详解.md STL C++ 二分查找库 二分查找库 闭区间、左闭右开区间和开区间 视频讲解二分法 class Solution {lower_bound 返回最小的满足 nums[i
概述
二分查找详解.md
STL C++ 二分查找库
二分查找库
闭区间、左闭右开区间和开区间
视频讲解二分法
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)
left = mid + 1; // 范围缩小到 [mid+1, right]
else
right = mid - 1; // 范围缩小到 [left, mid-1]
}
return left; // 或者 right+1
}
// 左闭右开区间写法
int lower_bound2(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)
left = mid + 1; // 范围缩小到 [mid+1, right)
else
right = mid; // 范围缩小到 [left, mid)
}
return left; // 或者 right
}
// 开区间写法
int lower_bound3(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)
left = mid; // 范围缩小到 (mid, right)
else
right = mid; // 范围缩小到 (left, mid)
}
return right; // 或者 left+1
}
public:
vector<int> searchRange(vector<int> &nums, int target) {
int start