C4.05 二分答案

课堂内容:

二分答案

"二分答案" 是一种算法策略，它常用于求解满足某种条件的最值问题。当问题的答案具有单调性时，即当某个参数增加或减少时，问题的答案也相应地增加或减少，我们可以使用二分答案策略。

基本思想：

1. 确定答案的范围。这通常是一个闭区间 [L, R]。

2. 在这个范围内进行二分，选择一个中间值 mid。

3. 根据问题的要求，检查 mid 是否满足条件。

4. 如果 mid 满足条件，则更新答案，并调整搜索范围到左半部分 [L, mid-1] 或右半部分 [mid+1, R]，具体取决于问题是求最大值还是最小值。

5. 如果 mid 不满足条件，同样调整搜索范围，但方向与第4步相反。

6. 重复步骤2-5，直到搜索范围为空或达到所需的精度。