本文介绍两类常见的区间搜索方法：二分查找用于单调条件，三分查找用于单峰函数的极值。写代码前先确认问题满足相应条件，再选择模板。

一、二分查找

1. 适用条件

给定一个升序数组 a，查找某个值或满足条件的边界。二分查找每次排除一半候选区间，时间复杂度为 O(log n)；数组必须有序，或待判断条件必须具有单调性。

2. 查找第一个大于等于 target 的位置

下面使用左闭右开区间 [left, right)。循环始终保持：答案如果存在，就在当前区间内。循环结束时，left 是第一个满足 a[i] >= target 的位置；若 left == n，则没有这样的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <bits/stdc++.h>
using namespace std;

int lowerBoundIndex(const vector<int>& a, int target) {
    int left = 0;
    int right = static_cast<int>(a.size());
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (a[mid] >= target) right = mid;
        else left = mid + 1;
    }
    return left;
}

例如 a = {1, 2, 2, 4}、target = 2，函数返回下标 1。若要找第一个大于 target 的位置，把判断条件改为 a[mid] > target，这正是标准库 upper_bound 的含义。

3. 查找一个值或最后一个不大于目标值的位置

拿到 lowerBoundIndex 的结果后，可以检查是否命中：

1
2
3
4
5
6
int pos = lowerBoundIndex(a, target);
if (pos < static_cast<int>(a.size()) && a[pos] == target) {
    // 找到了，pos 是第一个等于 target 的位置
} else {
    // 不存在
}

找最后一个不大于 target 的位置，可先找第一个大于 target 的位置，再减一；减一前要检查结果是否为零。

4. 二分答案

有些题目不是直接查数组，而是问“最小的可行值”或“最大的可行值”。如果答案范围有限，并且可行性具有单调性，就可以二分答案。

以“最小可行值”为例，定义 check(x) 表示“答案不超过 x 时能否完成任务”。若 check(x) 一旦为真，所有更大的值也为真，就寻找第一个使 check 为真的值：

1
2
3
4
5
6
7
8
9
long long firstFeasible(long long left, long long right) {
    // 前提：check(right) 为 true，且 check 单调不减
    while (left < right) {
        long long mid = left + (right - left) / 2;
        if (check(mid)) right = mid;
        else left = mid + 1;
    }
    return left;
}

使用前要自己证明单调性，并确认区间端点是否可行。二分答案的核心不是背模板，而是写对 check 和方向。

二、三分查找

1. 适用条件

三分查找用于区间内的单峰函数：函数先单调下降再单调上升（有唯一谷底），或先上升再下降（有唯一峰顶）。若函数有多个局部极值，不能直接使用。

2. 浮点数区间上的最小值

每轮取两个三等分点 m1、m2。若 f(m1) < f(m2)，谷底在 [left, m2]；否则谷底在 [m1, right]。重复缩小区间，直到达到所需精度。

1
2
3
4
5
6
7
8
9
10
double ternaryMin(double left, double right) {
    const double eps = 1e-7;
    while (right - left > eps) {
        double m1 = left + (right - left) / 3.0;
        double m2 = right - (right - left) / 3.0;
        if (f(m1) < f(m2)) right = m2;
        else left = m1;
    }
    return (left + right) / 2.0;
}

求最大值时比较方向相反。f 代表题目给出的函数，需要根据题意实现。

3. 整数区间上的最小值

整数答案不能只依赖浮点误差。区间缩小到少数几个点后，逐个计算并比较：

1
2
3
4
5
6
7
8
9
10
11
12
13
long long ternaryMinInteger(long long left, long long right) {
    while (right - left > 3) {
        long long m1 = left + (right - left) / 3;
        long long m2 = right - (right - left) / 3;
        if (f(m1) < f(m2)) right = m2 - 1;
        else left = m1 + 1;
    }
    long long answer = left;
    for (long long x = left + 1; x <= right; ++x) {
        if (f(x) < f(answer)) answer = x;
    }
    return answer;
}

三、如何选择

问题特征 方法
有序数组中找值或边界 二分查找
可行性随答案单调变化 二分答案
单峰函数上找极大值或极小值 三分查找

练习可以从洛谷的二分查找题单和三分法模板题开始。完成题目后，重点检查区间定义、循环终止条件、边界和单调性证明。