整数二分问题
作者:
VALUE_5
,
2021-10-31 18:39:48
,
所有人可见
,
阅读 241
单调一定可以二分,但二分不一定单调。
二分可用于找分界点,在分界点的左边满足某种约束,分界点的右边不满足。
l r
|-----------------------------|
|------------||---------------|
|--绿色性质--x
mid_t
mid_f
y-----红色性质--|
mid_f mid_t
(1)假设要找x分界点,x左边满足某种性质:
1、mid = (l + r + 1) >> 1
2、if(check(mid)) true [mid_t,r] 更新操作为:l = mid
false [l,mid_f-1] 更新操作为:r = mid - 1
(2)假设要找y分界点,y右边满足某种性质:
1、mid = (l + r)>>1
2、if(check(mid)) true [l,mid_t] 更新操作为:r = mid
false [mid_f+1,r] 更新操作为:l = mid + 1
# 如何选择模板,看check函数为真时区间的更新方式,若为:l = mid ,mid = (l + r + 1) >> 1
# r = mid ,mid = (l + r) >> 1