算法-二分答案

前言

二分查找是在一个有序数组中，每次查找将数组分成两半，并将查找值与中间值比较，是一个快速查找（$O(\log n)$）的方法。
例如，在 $[1, 2, 3, 4, 5, 5, 7]$ 中查找 $7$：

• 获取中间值 $4$，$4 \lt 5$，所以在右半边 $[5, 5, 7]$ 继续查找。
• 获取中间值 $5$，$5 \lt 7$，所以在右半边 $[7]$ 继续查找。
• 数组中只有一个元素 $7$，查找完成。

二分答案与其非常相似，是在一个具有单调性的问题中，查找最值的方法。

基本思想

单调性

什么问题具有单调性呢？

以下是几个具有单调性的问题：

• 数字炸弹（伪）：已知数字 $x \in [1,n]$ 后全是炸弹，求出最后一个安全位置。
• [NOIP2015 提高组] 跳石头：已知隔一段距离有一块石头，求出拆除 $x$ 个石头后，最近两块石头间距离的最大值。

以上问题都有共同点：

• 问题有确定的边界。
• 一定程度上，当 $x$ 满足条件时，比 $x$ 大或小的数不满足条件。

处理问题

根据以上性质，可以按以下思路求解：

• 首先，给出一段区间 $[1,N]$。
• 之后，求出中间值 $mid$，并验证答案为 $mid$ 时是否满足条件。
• 根据单调性，缩小区间。

注意事项

在使用二分答案过程中，需要注意以下问题：

• 初始区间应该含最终结果。
• 注意不能出现死循环。
• 编写正确的验证答案算法。

补充

对上述“数字炸弹（伪）”的演示：

已知在 $[1,100]$ 的整数中，$78$ 以后是炸弹，求出最大的安全位置。

虽然显然安全位置等于 $78-1$，但是此处为了演示，使用二分答案。

• 定义二分搜索的上下界：下界是 $1$，上界是 $100$。

• 二分搜索：在每一步中，我们计算中间值 $mid$，并检查它是否是安全位置（即是否小于或等于 $78$）。

• 调整搜索范围：

  • 如果 $mid$ 是安全位置，并且我们希望找到尽可能大的安全位置，那么我们将下界更新为 $mid + 1$ 并继续搜索。
  • 如果 $mid$ 不是安全位置，那么我们将上界更新为 $mid - 1$。

• 终止条件：当上下界相遇或错过时，搜索结束。

以下是演示：

• $l=1,r=100,mid=50$，此时 $mid$ 为较小值，$l \rightarrow mid + 1$。
• $l=51,r=100,mid=75$，此时 $mid$ 为较小值，$l \rightarrow mid + 1$。
• $l=76,r=100,mid=88$，此时 $mid$ 为较大值，$r \rightarrow mid - 1$。
• $l=76,r=87,mid=81$，此时 $mid$ 为较大值，$r \rightarrow mid - 1$。
• $l=76,r=80,mid=78$，此时 $mid$ 为较大值，$r \rightarrow mid - 1$。
• $l=76,r=77,mid=76$，此时 $mid$ 为较小值，$l \rightarrow mid + 1$。
• $l=77,r=77,mid=77$，此时 $l=r$，查找结束。所求值为 $77$。