在刷题或者写代码的时候lower_bound和upper_bound是两个非常高频但又容易用错的函数。很多人知道“能用”但不知道“为什么这样用”。这篇文章不搞花里胡哨的定义直接从实际理解、使用方式、常见坑这几个角度讲清楚。这两个函数到底是干嘛的一句话版本在一个有序序列中lower_bound找到第一个 x 的位置upper_bound找到第一个 x 的位置记住这句话基本就够用了。举个最简单的例子vectorint v {1, 2, 2, 2, 3, 4};查找2lower_bound(v.begin(), v.end(), 2) → 指向第一个 2 upper_bound(v.begin(), v.end(), 2) → 指向第一个 3也就是说lower_bound → 左边界 upper_bound → 右边界返回的是什么别搞错了这两个函数返回的不是下标而是迭代器iterator如果你要下标需要这样写int pos lower_bound(v.begin(), v.end(), x) - v.begin();最常见用途一判断元素是否存在auto it lower_bound(v.begin(), v.end(), x); if (it ! v.end() *it x) { cout 存在; }解释lower_bound 找到第一个 x 的位置如果这个位置刚好等于 x → 说明存在最常见用途二统计某个数出现次数int cnt upper_bound(v.begin(), v.end(), x) - lower_bound(v.begin(), v.end(), x);这行代码非常经典直接记住出现次数 右边界 - 左边界最常见用途三插入位置如果你要往有序数组中插入一个元素auto it lower_bound(v.begin(), v.end(), x); v.insert(it, x);这样插入之后数组依然有序。必须注意的前提一定要有序这两个函数的前提是序列必须是有序的默认升序如果是乱序数组结果是错的但不会报错这是最坑的地方自定义排序怎么办如果你用的是自定义排序比如降序sort(v.begin(), v.end(), greaterint());那你就必须传入同样的比较函数lower_bound(v.begin(), v.end(), x, greaterint());否则结果是错误的。手写理解它本质就是二分可以用一个简单的“手写版本”来理解 lower_boundint l 0, r n; while (l r) { int mid (l r) / 2; if (v[mid] x) r mid; else l mid 1; }最终l 就是 lower_bound 的位置而 upper_bound 只是把条件改成v[mid] x常见坑总结; 忘了数组必须有序很多人直接用在乱序数组上结果完全不对; 把返回值当下标记住它返回的是迭代器; 边界没判断it ! v.end()一定要写; 自定义排序没传比较函数这是中高级选手最容易翻车的地方一句话记忆法如果你懒得记一堆东西就记这一句lower_bound 找“第一个不小于”upper_bound 找“第一个大于”最后这两个函数本质上就是“封装好的二分查找”但它们的威力在于写法简洁不容易出错能直接解决很多区间问题建议你多用几次比如统计区间去重处理LIS最长上升子序列用多了自然就顺手了。