二分整理（经验？）

常规
1

介绍

二分的题目一般都隐藏了单调性的条件， 而要求的一般是形如“最大的最小值”， “最小的最大值”之类的东西。由此我们可以得到：题中数据有单调性并且答案要求一个极限值时适用二分法

模板

众所周知， 记二分中的+1/ -1、不等号能不能等是一件非常蛋疼的事情，因此建议背过模板。

整数二分模板：

while(l <= r)
{
    mid = l + r >> 1;
    if(check(mid)) l = mid + 1, res = mid;
    else r = mid - 1;
}

小数二分模板：

while(l <= r)
{
    mid = (l + r) / 2;//小数可能不能用位移（我猜的）
    if(check(mid)) l = mid, res = mid;
    else r = mid;
}

分析

由于是折半查找， 最优的时间复杂度为O(1), 最坏情况下的时间复杂度为O(logn)

代码中的check()函数视题目而定， 一般由贪心来实现check()。（但是出错最多的也是check()， 调错真的很讨厌啊）

2 个赞
2

催更分数规划和整体二分

2 个赞
3

你这头像让我想到了洛谷的 594203

2 个赞