跳到主要内容

二分与三分算法 (Binary & Ternary Search)

算法核心范式

二分与三分算法是处理有序性 (Order) 与 凸性 (Convexity) 问题的核心范式。其本质是通过对决策空间的重复划分，实现搜索复杂度的对数级 (O(log⁡n)O(\log n)) 压缩。

一、 二分算法：二分性与单调性证明​

1. 二分性定义 (Bisection Property)​

设 DD 为一个全序集，P:D→{0,1}P: D \to \{0, 1\} 为定义在 DD 上的布尔谓词。

定理 (二分性判定)： 若存在 m∈Dm \in D，使得 ∀x<m,P(x)=v1\forall x < m, P(x) = v_1 且 ∀x≥m,P(x)=v2\forall x \ge m, P(x) = v_2 (v1≠v2v_1 \neq v_2)，则称 PP 在 DD 上具有二分性。二分算法的目标即是在 O(log⁡∣D∣)O(\log |D|) 时间内找到该分界点 mm。

2. 系统化单调性证明范式​

在实际建模中，我们需要证明谓词 P(x)P(x) 的单调性以确保二分性的成立：

  • 直接证明法：证明若 P(x)P(x) 为真，则对于所有 x′>xx' > x，P(x′)P(x') 亦为真。
  • 资源单调性：证明若花费 xx 资源能达成目标，则花费 x+1x+1 资源必然也能达成目标。
  • 贡献单调性：证明随着自变量 xx 增加，其对目标的贡献是单调非减的。
超越单调性：局部二分性

二分算法的本质是二分性。即使谓词 PP 不全局单调，只要我们能根据局部性质判定答案所在的一侧，二分依然有效。 典型案例：寻找山峰元素 —— 数组无序，但利用 a[i]<a[i+1]a[i] < a[i+1] 这一局部性质可引导搜索方向。

二、 整数二分的收敛性分析与正确性证明​

1. 算法正确性的形式化证明 (Floyd-Hoare Logic)​

对于寻找满足 P(x)P(x) 的最小整数 xx 的算法，其正确性由以下三个要素支撑：

  • 初始化 (Initialization)：初始区间 [l,r][l, r] 必须包含目标解。
  • 保持 (Maintenance)：若 P(mid)P(mid) 为真，则目标解 ≤mid\le mid，更新 r=midr = mid；否则目标解 >mid> mid，更新 l=mid+1l = mid + 1。无论哪种情况，目标解始终保持在 [l,r][l, r] 内。
  • 终止 (Termination)：每次迭代后区间长度 Lnew≤⌈Lold/2⌉L_{new} \le \lceil L_{old}/2 \rceil。由于 LL 是正整数序列且严格递减，算法必将在 L=1L=1 即 l=rl=r 时终止。

2. 收敛速度与复杂度分析​

二分搜索是一个典型的对数时间算法。 设初始空间大小为 NN，第 kk 次迭代后的空间大小为 Nk=N/2kN_k = N/2^k。 当 Nk=1N_k = 1 时，迭代停止： N2k=1  ⟹  k=log⁡2N\frac{N}{2^k} = 1 \implies k = \log_2 N 这意味着无论数据量如何翻倍，搜索次数仅线性增长。这在计算机科学中被视为“近乎常数级”的高效。

3. 边界处理：防止死循环的数学原理​

在整数除法 (l+r)/2 默认下取整的机制下：

类型目标区间更新mid 计算关键逻辑适用场景
左边界型r=mid,l=mid+1r=mid, l=mid+1l + r >> 1保持 rr 指向合法解寻找第一个满足 PP 的位置
右边界型l=mid,r=mid−1l=mid, r=mid-1l + r + 1 >> 1保持 ll 指向合法解寻找最后一个满足 PP 的位置

死循环证明：当 l=r−1l = r-1 时，若使用下取整 mid = l。若执行 l = mid，则 ll 保持不变，区间 [l,r][l, r] 无法收敛。因此右边界型二分必须上取整 (l+r+1)/2。

三、 实数二分与三分：精度与收敛分析​

1. 实数二分的精度控制​

实数二分不存在整数边界问题，但面临浮点数精度限制。常用的两种停止准则：

  • 固定精度：while (r - l > eps)。通常 epseps 取 10−k−210^{-k-2}（若要求保留 kk 位小数）。
  • 固定次数：for (int i = 0; i < 100; i++)。迭代 100 次可将区间缩小 2100≈10302^{100} \approx 10^{30} 倍，足以应对绝大多数工程与竞赛需求。

2. 三分算法：凸性与极值搜索​

对于单峰（或单谷）函数，三分法利用两个采样点 m1,m2m_1, m_2 排除 1/31/3 的搜索空间。

收敛分析： Lk=(23)kL0L_k = \left(\frac{2}{3}\right)^k L_0 由于 2/3>1/22/3 > 1/2，三分法的收敛速度略慢于二分法。在 O(1)O(1) 的函数评估成本下，二分导数（若可求导）通常优于三分。

四、 教材化例题​

例题 1：寻找峰值 (Peak Finding)​

给定一个相邻元素不相等的数组，找到任意一个局部峰值 a[i−1]<a[i]>a[i+1]a[i-1] < a[i] > a[i+1]。

决策推导与严密证明

单调性证明（局部）： 考虑 midmid 与 mid+1mid+1 的关系。

  1. 若 a[mid]<a[mid+1]a[mid] < a[mid+1]，说明 midmid 处于上升段，且由于数组边界为 −∞-\infty，右侧一定存在峰值。
  2. 若 a[mid]>a[mid+1]a[mid] > a[mid+1]，说明 midmid 处于下降段，左侧一定存在峰值。 二分性：基于局部斜率引导搜索，单向收敛。
int findPeakElement(vector<int>& nums) {
    int l = 0, r = nums.size() - 1;
    while (l < r) {
        int mid = l + r >> 1; // 下取整
        if (nums[mid] < nums[mid + 1]) l = mid + 1; // 峰值在右侧
        else r = mid; // 峰值在左侧（含mid）
    }
    return l;
}

例题 2：进击的奶牛 (Aggressive Cows)​

NN 个牛舍在一条直线上，坐标为 xix_i。安置 CC 头牛，使它们之间的最近距离最大。

判定性构造与单调性证明

1. 谓词定义：P(d)P(d) 表示是否存在一种方案，使所有相邻牛的距离 ≥d\ge d。 2. 单调性证明：若 dd 合法，则对于任意 d′<dd' < d，显然也合法。P(d)P(d) 在定义域上单调。 3. 判定函数 (Check)：贪心放置。从第一间牛舍开始，每隔至少 dd 距离放置一头牛。

bool check(int d, vector<int>& x, int c) {
    int cnt = 1, last = x[0];
    for (int i = 1; i < x.size(); i++) {
        if (x[i] - last >= d) {
            cnt++;
            last = x[i];
        }
    }
    return cnt >= c;
}

int main() {
    sort(x.begin(), x.end());
    int l = 0, r = 1e9;
    while (l < r) {
        int mid = l + r + 1 >> 1; // 右边界型二分
        if (check(mid, x, c)) l = mid;
        else r = mid - 1;
    }
    cout << l << endl;
}

五、 综合练习库​

练习 1：旋转排序数组中的最小值​

一个升序数组被旋转（如 [4,5,6,7,0,1,2]）。找到其中最小值。

Check Solution

二分性证明： 比较 nums[mid] 与 nums[r]。

  1. 若 nums[mid] < nums[r]，说明右半段有序且最小值在左侧（含 midmid）。
  2. 若 nums[mid] > nums[r]，说明最小值在右侧且 midmid 不是最小值。
int findMin(vector<int>& nums) {
    int l = 0, r = nums.size() - 1;
    while (l < r) {
        int mid = l + r >> 1;
        if (nums[mid] < nums[r]) r = mid;
        else l = mid + 1;
    }
    return nums[l];
}

练习 2：砍树 (EKO)​

NN 棵树高度 HiH_i，需得到 MM 米木材。锯片高度设为 HH，求最大 HH。

Check Solution

单调性：HH 越低，木材越多。

long long get_wood(int h, vector<int>& trees) {
    long long sum = 0;
    for (int t : trees) if (t > h) sum += t - h;
    return sum;
}

// 二分 H
int l = 0, r = 1e9;
while (l < r) {
    int mid = l + r + 1 >> 1;
    if (get_wood(mid, trees) >= M) l = mid;
    else r = mid - 1;
}

练习 3：寻找实数极值 (三分法)​

求 f(x)=x4−2x2+5f(x) = x^4 - 2x^2 + 5 在 [0,2][0, 2] 上的最小值。

Check Solution
double l = 0, r = 2;
for (int i = 0; i < 100; i++) {
    double m1 = l + (r - l) / 3;
    double m2 = r - (r - l) / 3;
    if (f(m1) < f(m2)) r = m2;
    else l = m1;
}
printf("%.10f\n", f(l));

编者注：二分搜索的精髓在于“审判”。每一次 check 都是对真理边界的一次剥离。如果你无法证明单调性，请寻找局部二分性。