二分算法

整数二分

有单调性一定可以二分查找，可以二分查找的不一定要求有单调性。

二分的本质：

• 给定一个区间 [l, r]
• 其中 [l, t] 满足某个 性质，[t + 1, r] 不满足该性质
• 则可以使用二分查找的方式找到这个边界点 t

算法流程：

• 找中间值 mid = (l + r) / 2
• 判断中间值是否满足该性质 check(mid)
  • 满足：说明 mid 落在 [l, t] 中，即 t >= mid，下一个二分区间为 [mid, r]，即 l = mid
  • 不满足：说明 mid 落在 [t + 1, r] 中，即 t < mid，下一个二分区间为 [l, mid - 1]，即 r = mid - 1
• 此算法可以找到 最后一个满足该性质 的边界点

另外一种情况：假如 [l, t - 1] 不满足某个性质，而 [t, r] 均满足某个性质

• 找中间值 mid = (l + r) / 2
• 判断中间值是否满足该性质 check(mid)
  • 满足：说明 mid 落在 [t, r] 中，即 t <= mid，下一个二分区间为 [l, mid]，即 r = mid
  • 不满足：说明 mid 落在 [l, t - 1] 中，即 mid < t，下一个二分区间为 [mid + 1, r]，即 l = mid + 1
• 此算法可以找到 第一个满足该性质 的边界点

这里还有一些边界问题需要处理，不过我们先讨论二分问题的思考套路：

• 先写出该二分问题的 check 函数
• 然后判断该怎么更新区间
• 根据更新区间的不同来修改中间值，l = mid 就需要补一个 + 1（这一步之后解释）

我们知道，C++ 中的取整都是向下取整，因此当区间中的整数个数是偶数时，mid = (l + r) / 2 将会取到中间两个数中较小的那个数，而 mid = (l + r + 1) / 2 将会取到中间两个数中较大的那个数。

以 l = r - 1 这样一个两个数为例，如果 mid = (l + r) / 2，那么 mid = l，此时如果下一个二分区间为 [mid, r], [l, mid - 1] 即为 [l, r], [l, l - 1] 出现问题。而如果改为 mid = (l + r + 1) / 2，那么 mid = r，此时下一个二分区间为 [mid, r], [l, mid - 1] 即为 [r, r], [l, l] 没有问题。另一种情况同理可以讨论。

综上所述：

• l = mid; r = mid - 1：对应 [l, mid - 1], [mid, r]，此时 mid = (l + r + 1) / 2
• r = mid; l = mid + 1：对应 [l, mid], [mid + 1, r]，此时 mid = (l + r) / 2
• 存在 - 1 就存在 + 1，这样比较好记

AC789

浮点数二分

浮点数二分不需要处理边界，只需要保证答案落在下一次二分的区间内部即可，当区间长度 r - l 足够小时就找到了答案。

或者直接循环 100 次，也就是将区间长度缩小到原来的 2^100，也是可以的。