新写的笔记，给萌友们尝尝鲜
是关于二分查找的，不多说，自己看吧。
如果要在一个有序数组里寻找第一个大于等于 target 的元素下标，最直觉的写法就是遍历，但是这样的复杂度是 O(n)，在大数据下较劣。原因是，没有利用到数组有序这个性质。
二分查找（binary search）是一种能在有序数组中快速找到指定元素的算法。它每次将搜索范围减小一半，因此非常高效。时间复杂度通常为 O(log n)。
但这么高效的算法是陷阱密布的。接下来我想用尽可能简单的语言避开二分查找的每一个坑点。
在这之前必须了解几个常用的库函数，它们都在 <algorithm> 头文件中。
vector<int> v;
/* 一些初始化代码 */
auto i = lower_bound(v.begin(), v.end(), elem);
auto j = upper_bound(v.begin(), v.end(), elem);
也可以是
auto i = ranges::lower_bound(v, elem);
auto j = ranges::upper_bound(v, elem);
或者
auto [i, j] = ranges::equal_range(v, elem);
其中 i 和 j 会返回一个迭代器，分别代表数组中第一个大于或等于 elem 的位置和第一个严格大于 elem 的位置。
我们希望自己实现一个二分查找，因此这里仅作了解，下面是正式部分。
红蓝染色法
我们在本篇所说的二分查找都是在一个非严格递增顺序的数组中寻找大于等于 target 的数，简单记为 lowerbound()。
二分查找的写法按照区间来划分可以有三种：闭区间、左闭右开区间和开区间。
所谓闭区间，意思是在 [l, r] 这个下标区间内，所有的元素都无法确定大小。左闭右开区间是 [l, r)，开区间则是 (l, r)。这里先说闭区间。
标题中的红蓝染色法是一种二分查找常用的标记元素的方法。先看下面的例子。
给你一个按照非递减顺序排列的整数数组
nums，和一个目标值target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值
target，返回[-1, -1]。你必须设计并实现时间复杂度为
O(log n)的算法解决此问题。
这是原题给的样例。
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
红蓝染色法简单来说，就是将所有严格小于 target 的部分染成红色块，大于或等于 target 的部分染成蓝色块，这样最终第一个蓝色块就是 lowerbound() 的返回值了。
下面是这个流程的图示。
这就是我们所说的红蓝染色法。
同时闭区间 [l, r] 以外的元素都是已经确定好会被排除的元素。换言之，我们写闭区间的二分查找，本质上就是保证 [r+1, nums.size()] 中的元素大于等于 target，而 [0,l-1] 中的元素小于 target。上一句话很重要，这就是确保二分查找不出现死循环的关键。
同时注意，C++ 中如果 nums 的长度到了 int 类型最大值，使用 m = (l+r) / 2 就会导致溢出，解决方案是换成 m = l + (r - l) / 2。
class Solution {
int lowerbound(vector<int>& nums, int target) {
int l = 0, r = nums.size() - 1;
while (l <= r) { // 保证区间不为空
int m =
l + (r - l) / 2; // 防止溢出，Python 可以写为 m = (r + l) // 2
if (nums[m] >= target) { // 大于或等于 target，更新 r
r = m - 1;
} else { // 严格小于 target，更新 l
l = m + 1;
}
}
return l;
}
public:
vector<int> searchRange(vector<int>& nums, int target) {
// 实际上就是返回第一个大于等于 target 的元素对应的下标
// 还有第一个严格大于 target 的元素对应的下标减去 1
int start = lowerbound(nums, target);
if (start == nums.size() || nums[start] != target) { // 前者为了防空数组，后者防数组中不存在 target
return {-1, -1};
}
int end = lowerbound(nums, target + 1) - 1;
return {start, end};
}
};
在 nums 中寻找最后一个大于等于 target 元素对应的下标，等价于寻找第一个严格大于 target 的元素对应的下标减去 1。
以此类推，可以写出一张针对不同情况的二分查找调用方式。
