c++中如何实现二分查找_c++二分查找算法实现
std::lower_bound和std::upper_bound可直接用于二分查找：前者找首个≥target位置，后者找首个>target位置，二者结合得target的完整迭代器范围，适用于随机访问容器。
std::lower_bound 和 std::upper_bound 能直接用，别手写循环
绝大多数场景下，std::lower_bound 和 std::upper_bound 就是你要的二分查找。它们要求容器已排序（或传入相同比较器），时间复杂度 O(log n)，且经过标准库充分测试，边界处理比手写更可靠。
- 查第一个 ≥ target 的位置 → 用
std::lower_bound - 查第一个 > target 的位置 → 用
std::upper_bound - 两者结合可得 [first, last) 区间内所有 target 的迭代器范围
- 对
std::vector、普通数组指针、std::array都适用，只要支持随机访问迭代器
手写 while 循环时，left
取决于你定义的搜索区间是闭区间 [left, right] 还是左闭右开 [left, right)。前者常用 left ，后者必须用 left 。混用会导致死循环或越界。
- 闭区间写法：初始化
right = vec.size() - 1，循环条件left ，更新时right = mid - 1/left = mid + 1 - 左闭右开写法：初始化
right = vec.size()，循环条件left ，更新时right = mid/left = mid + 1 - 返回值含义不同：闭区间若未找到通常返回
-1；左闭右开习惯返回left（即插入位置），需额外判断vec[left] == target
自定义比较函数时，operator
如果你的容器元素不是基础类型（比如 struct 或 class），或想按特定字段查找，必须确保 std::lower_bound 的第三个参数（比较函数）与容器排序所用逻辑完全一致。否则行为未定义。
- 排序用了
std::sort(vec.begin(), vec.end(), [](const auto& a, const auto& b) { return a.id - 查找也得用同签名的 lambda：
std::lower_bound(vec.begin(), vec.end(), target_id, [](const auto& e, int id) { return e.id - 注意参数顺序：比较函数应为
(value_type, T)或(T, value_，取决于你是查“小于 target”还是“target 小于某值”——
type)
lower_bound要求的是comp(value, target) == true表示value在target前
#include#include #include struct Person { int id; std::string name; };
int main() { std::vector
people = {{1,"Alice"}, {3,"Bob"}, {5,"Charlie"}, {7,"Diana"}}; // 按 id 排序（已满足） int target = 5; auto it = std::lower_bound(people.begin(), people.end(), target, [](const Person& p, int id) { return p.id zuojiankuohaophpcn id; }); if (it != people.end() && it-youjiankuohaophpcnid == target) { std::cout zuojiankuohaophpcnzuojiankuohaophpcn "Found: " zuojiankuohaophpcnzuojiankuohaophpcn it-youjiankuohaophpcnname zuojiankuohaophpcnzuojiankuohaophpcn "\n"; } else { std::cout zuojiankuohaophpcnzuojiankuohaophpcn "Not found\n"; }}
浮点数二分要小心精度和终止条件
对浮点数做二分（比如解方程、找阈值），不能依赖
left == right终止。必须设定精度容差（如1e-6）或最大迭代次数，否则可能死循环。
- 避免用
while (left 直接比较浮点数- 推荐用迭代次数控制：
for (int i = 0; i —— 100 次足够把区间缩小到1e-30级别- 或者用
while (right - left > eps)，但需确保eps大于浮点数的机器精度（std::numeric_limits是相对误差，不适用于此）::epsilon() - mid 计算建议用
mid = left + (right - left) / 2.0，避免left + right溢出（对 double 影响小，但写成习惯更安全）实际用的时候，先看能不能走
std::lower_bound；非要手写，就盯死区间定义和终止条件；查浮点数，别信相等判断。
