二分法中mid的处理以及STL二分函数

2023-12-14 03:55:52

若我们需要在单调递增序列中找 x 或 x 的后继 的 mid 计算方法：

? ? ? ? ?实现? 使用场合可能出现的问题????????
mid = (left + right) / 2

left >= 0, right >= 0,

left + right无溢出

left + right可能溢出

负数情况下有向0取整问题

mid = left + (right-left)/2right - left 无溢出? ? ?若right 和left都是大数且一正一负,right - left可能溢出
mid = (left + right) >> 1left + right无溢出若left和right都为大数,left + right可能溢出

三种方法各有优缺点，综合起来，mid = (left + right) >> 1 更好一些

若需要找 x 或 x 的前驱，则用 mid = (left + right + 1) >> 1 即可

关于对应的STL函数：

（1）upper_bound() : 查找第一个大于 x 的元素的位置，pos = upper_bound(a, a + n, x) - a；

（2）lower_bound() : 查找第一个等于或大于 x 的元素；

（3）upper_bound() - lower_bound() : 计算单调序列中 x 的个数。

文章来源:https://blog.csdn.net/m0_60936523/article/details/134839518
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。