当在一个有序序列中查找某个元素时,lower_bound
和 upper_bound
是两个非常有用的函数。
lower_bound
函数:lower_bound(first, last, val)
函数返回的是序列中第一个大于或等于val
的元素的位置。- 如果序列中不存在大于或等于
val
的元素,则返回的是last
的位置。 - 如果序列中有多个等于
val
的元素,lower_bound
返回的是第一个等于val
的元素的位置。
数学表示:$ \text{lower_bound}(v, val) = \text{min}\{i | v_i \geq val\} $
upper_bound
函数:upper_bound(first, last, val)
函数返回的是序列中第一个大于val
的元素的位置。- 如果序列中不存在大于
val
的元素,则返回的是last
的位置。
数学表示:$ \text{upper_bound}(v, val) = \text{min}\{i | v_i > val\} $
总结:
- lower_bound
返回的是第一个大于或等于目标值的位置,如果不存在,则返回的是last
的位置。
- upper_bound
返回的是第一个大于目标值的位置,如果不存在,则返回的是last
的位置。
这两个函数通常与std::binary_search
结合使用,可以帮助在有序序列中进行高效的查找操作。