二分答案题型总结

什么时候想到二分答案

当题目问的是“最大值最小”“最小值最大”这类极值问题时，就可以先问自己一句：

如果我猜一个答案，能不能在线性或对数时间内验证它是否可行？

如果可以，通常就能二分。

经典结构

while (left < right) {
    int mid = left + (right - left) / 2;
    if (check(mid)) {
        right = mid;
    } else {
        left = mid + 1;
    }
}

经验

• 先判断是找“第一个真”还是“最后一个真”。
• check() 的单调性必须成立，不然二分没有意义。
• 边界的定义要在写代码前说清楚。

推荐的写法习惯

• 注释掉 left 和 right 的含义
• 单独写 check
• 用样例手推三轮确认边界变化