std::lower_bound用于有序数组中查找第一个不小于目标值的元素下标，返回迭代器需转为下标，时间复杂度O(log n)；使用时需确保数组升序、处理边界情况，并注意与upper_bound的区别及插入开销。
用 std::lower_bound 直接获取插入位置
有序数组中找插入位置，本质是找第一个不小于目标值的元素下标——这正是 std::lower_bound 的语义。它返回迭代器，减去起始迭代器就是下标，时间复杂度 O(log n)，且无需手写二分逻辑。
常见错误是误用 std::upper_bound（它返回第一个大于目标值的位置），或对空数组、全小于/全大于目标的情况没做边界检查。
- 数组必须严格升序（或按同一比较规则有序），否则行为未定义
- 若目标值已存在，
std::lower_bound返回其首次出现位置，符合“插入后仍有序”的要求 - 注意返回的是迭代器，转下标要写
it - vec.begin()，不是it - &vec[0]（后者对 vector 不安全）
vector<int> arr = {1, 3, 5, 6};
int target = 5;
auto it = lower_bound(arr.begin(), arr.end(), target);
int pos = it - arr.begin(); // pos == 2
手写二分时为什么左闭右开区间更稳妥
很多教程用左闭右闭（[left, right]），但容易在 left == right 时陷入死循环或漏判边界；左闭右开（[left, right)）统一用 while (left < right)，每次缩小区间都明确排除一个位置，逻辑更清晰。
关键点在于：右边界始终不参与比较，所以 right 初始化为 n（数组长度），而非 n-1；更新时 right = mid 而非 mid - 1。
立即学习“C++免费学习笔记（深入）”；
- 当
arr[mid] < target，说明插入位置一定在mid+1右侧，所以left = mid + 1 - 当
arr[mid] >= target，mid本身可能是答案，所以保留mid，即right = mid - 循环结束时
left == right，该下标就是插入位置
处理重复元素时 lower_bound 和 upper_bound 的区别
如果数组含重复值（如 {1,2,2,2,3}），std::lower_bound 返回第一个 2 的位置，std::upper_bound 返回最后一个 2 后面的位置。插入位置取决于需求：
- 想保持相等元素相对顺序（稳定插入），用
lower_bound - 想插到所有相同元素之后（例如实现 multiset 的等价插入），用
upper_bound - 两者返回位置差值，就是该值在数组中的出现次数
vector<int> arr = {1,2,2,2,3};
int pos1 = lower_bound(arr.begin(), arr.end(), 2) - arr.begin(); // 1
int pos2 = upper_bound(arr.begin(), arr.end(), 2) - arr.begin(); // 4
原地插入元素前必须检查容量和移动开销
std::lower_bound 只给出位置，真正调用 vec.insert(it, val) 会触发后续元素整体后移，复杂度 O(n)。如果只是查找位置，别盲目插入；如果真要插入，注意：
-
vector插入可能触发内存重分配，提前reserve可避免多次拷贝 - 若数组是裸指针（如
int*），插入需手动memmove，且必须确保有足够空间 - 对于只读场景，返回下标即可；频繁插入建议换用
std::set或std::multiset
最常被忽略的是：函数返回插入位置，不等于该位置当前有有效元素——越界下标（如 pos == arr.size()）是合法的插入尾部位置，但直接 arr[pos] 访问会崩溃。
