第四章搜索与二分¶

本章目标：掌握二分查找的多种变体（整数二分、浮点二分、二分答案、三分搜索），熟练运用 BFS/DFS 遍历图与树，理解 Flood Fill、剪枝与折半搜索技巧，并能综合运用搜索策略解决竞赛问题。

4.1 二分查找原理与实现¶

4.1.1 二分查找的基本思想¶

二分查找适用于单调性问题：在一个有序序列中，通过每次排除一半的元素，快速定位目标值。

graph LR
    A["有序数组: 1 3 5 7 9 11"] --> B["查找 7: mid=5, 5<7, 向右"]
    B --> C["区间 7 9 11: mid=9, 9>7, 向左"]
    C --> D["区间 7: 找到!"]

核心公式：

mid = (l + r) / 2（向下取整）
mid = l + (r - l) / 2（防溢出写法）

4.1.2 整数二分¶

整数二分有两种常见模板，区别在于区间的开闭和 mid 的归属。

模板一：寻找左边界（满足条件的最小值）¶

// 在 [l, r] 中找到第一个满足 check(mid) == true 的位置
int binarySearchLeft(int l, int r) {
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (check(mid)) r = mid;      // mid 可能是答案，保留
        else l = mid + 1;              // mid 不满足，排除
    }
    return l;  // l == r，即为答案
}

模板二：寻找右边界（满足条件的最大值）¶

// 在 [l, r] 中找到最后一个满足 check(mid) == true 的位置
int binarySearchRight(int l, int r) {
    while (l < r) {
        int mid = l + (r - l + 1) / 2;  // 注意 +1 防止死循环
        if (check(mid)) l = mid;          // mid 可能是答案，保留
        else r = mid - 1;                 // mid 不满足，排除
    }
    return l;  // l == r，即为答案
}

两种模板的关键区别

模板	mid 计算	check 为 true 时	check 为 false 时
左边界	`(l+r)/2`	`r = mid`	`l = mid + 1`
右边界	`(l+r+1)/2`	`l = mid`	`r = mid - 1`

记忆口诀：右边界模板的 mid 要 +1，否则当 l + 1 == r 时 mid == l，若 check(mid) 为 true 则 l = mid（即 l 不变），造成死循环。

完整示例：查找元素的起始和结束位置¶

#include <bits/stdc++.h>
using namespace std;

// 在有序数组中查找 target 的起始和结束位置
vector<int> searchRange(vector<int>& nums, int target) {
    int n = nums.size();
    if (n == 0) return {-1, -1};

    // 找左边界：第一个 >= target 的位置
    int lo = 0, hi = n - 1;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] >= target) hi = mid;
        else lo = mid + 1;
    }
    if (nums[lo] != target) return {-1, -1};
    int left = lo;

    // 找右边界：最后一个 <= target 的位置
    hi = n - 1;  // lo 不需要重置（从 left 开始搜索更快）
    while (lo < hi) {
        int mid = lo + (hi - lo + 1) / 2;
        if (nums[mid] <= target) lo = mid;
        else hi = mid - 1;
    }
    return {left, lo};
}

int main() {
    vector<int> nums = {5, 7, 7, 8, 8, 10};
    auto res = searchRange(nums, 8);
    cout << res[0] << " " << res[1] << endl;  // 输出: 3 4
    return 0;
}

4.1.3 浮点二分¶

浮点二分用于求解连续值上的精确解（如开方、方程求根）。

#include <bits/stdc++.h>
using namespace std;

// 浮点二分求平方根
double sqrtBinary(double x) {
    double lo = 0, hi = max(1.0, x);  // 注意 x < 1 的情况
    while (hi - lo > 1e-9) {          // 精度要求 10^-9
        double mid = (lo + hi) / 2;
        if (mid * mid <= x) lo = mid;
        else hi = mid;
    }
    return lo;
}

// 浮点二分求方程 x^3 - x - 1 = 0 的根
double solveEquation() {
    double lo = 1, hi = 2;
    while (hi - lo > 1e-9) {
        double mid = (lo + hi) / 2;
        if (mid * mid * mid - mid - 1 <= 0) lo = mid;
        else hi = mid;
    }
    return lo;
}

int main() {
    cout << fixed << setprecision(6) << sqrtBinary(2.0) << endl;
    // 输出: 1.414214
    cout << fixed << setprecision(6) << solveEquation() << endl;
    // 输出: 1.324718
    return 0;
}

浮点二分的注意事项

循环终止条件是 hi - lo > eps（精度），而非 l < r
精度一般设为 1e-7 或 1e-9，根据题目要求调整
也可以固定循环次数（如 100 次），效果等价

4.1.4 STL 二分函数¶

C++ STL 提供了便捷的二分查找函数：

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> v = {1, 3, 5, 7, 9, 11};

    // 1. binary_search：判断元素是否存在
    bool found = binary_search(v.begin(), v.end(), 7);  // true

    // 2. lower_bound：第一个 >= target 的迭代器
    auto it1 = lower_bound(v.begin(), v.end(), 6);
    cout << *it1 << endl;  // 输出: 7

    // 3. upper_bound：第一个 > target 的迭代器
    auto it2 = upper_bound(v.begin(), v.end(), 7);
    cout << *it2 << endl;  // 输出: 9

    // 4. 计算元素出现次数
    vector<int> a = {1, 2, 2, 2, 3, 4};
    int cnt = upper_bound(a.begin(), a.end(), 2) - lower_bound(a.begin(), a.end(), 2);
    cout << cnt << endl;  // 输出: 3

    return 0;
}

函数	功能	复杂度
`binary_search`	判断是否存在	O(log n)
`lower_bound`	第一个 >= val	O(log n)
`upper_bound`	第一个 > val	O(log n)

4.2 二分答案（判定性问题）¶

核心思想¶

当直接求解最优解困难，但验证某个解是否可行很容易时，可以将求解问题转化为判定问题，用二分来缩小答案范围。

graph TD
    A["原问题：求最优值"] --> B["转化为：判定 mid 是否可行"]
    B --> C{"check(mid)"}
    C -->|可行| D["尝试更优: 调整区间"]
    C -->|不可行| E["排除 mid: 调整区间"]
    D --> F["最终答案"]
    E --> F

适用条件：

答案具有单调性：若 x 可行，则所有比 x 更优（或更差）的值也可行
存在高效的判定函数 check(mid)

经典模型¶

模型一：最小化最大值¶

问题：将数组分成 k 段，使得每段和的最大值最小。

思路：二分答案 mid（每段和的上限），贪心地判断能否在 k 段内完成。

#include <bits/stdc++.h>
using namespace std;

// 判定函数：能否将数组分成 <= k 段，每段和不超过 mid
bool check(vector<int>& nums, int k, long long mid) {
    int count = 1;       // 当前段数
    long long sum = 0;   // 当前段的和
    for (int x : nums) {
        if (x > mid) return false;  // 单个元素就超过 mid，不可能
        if (sum + x > mid) {
            count++;     // 开新段
            sum = x;
            if (count > k) return false;  // 超过 k 段
        } else {
            sum += x;
        }
    }
    return true;
}

// 二分答案：最小化分成 k 段后各段和的最大值
int splitArray(vector<int>& nums, int k) {
    long long lo = 0, hi = 0;
    for (int x : nums) {
        lo = max(lo, (long long)x);  // 下界：最大单个元素
        hi += x;                       // 上界：全部放在一段
    }

    while (lo < hi) {
        long long mid = lo + (hi - lo) / 2;
        if (check(nums, k, mid)) hi = mid;   // 可行，尝试更小
        else lo = mid + 1;                     // 不可行，增大
    }
    return lo;
}

int main() {
    vector<int> nums = {7, 2, 5, 10, 8};
    cout << splitArray(nums, 2) << endl;  // 输出: 18
    // 分成 {7,2,5} 和 {10,8}，最大段和 = 18
    return 0;
}

模型二：最大化最小值¶

问题：在一条直线上有 n 个点，要放置 k 个点，使得相邻放置点之间的最小距离最大。

思路：二分答案 mid（最小距离），贪心地判断能否放置 k 个点使得间距 >= mid。

#include <bits/stdc++.h>
using namespace std;

// 判定函数：能否放置 k 个点使得相邻间距 >= mid
bool check(vector<int>& pos, int k, int mid) {
    int count = 1;          // 放了第一个点
    int last = pos[0];      // 上一个放置位置
    for (int i = 1; i < pos.size(); i++) {
        if (pos[i] - last >= mid) {
            count++;
            last = pos[i];
            if (count >= k) return true;
        }
    }
    return false;
}

// 二分答案：最大化最小距离
int maxMinDistance(vector<int>& pos, int k) {
    sort(pos.begin(), pos.end());
    int lo = 1;                          // 最小距离至少为 1
    int hi = pos.back() - pos.front();   // 最大距离

    while (lo < hi) {
        int mid = lo + (hi - lo + 1) / 2;  // 右边界模板
        if (check(pos, k, mid)) lo = mid;
        else hi = mid - 1;
    }
    return lo;
}

模型三：满足条件的第 k 小/大¶

问题：给定一个 n x m 的乘法表，求第 k 小的数。

#include <bits/stdc++.h>
using namespace std;

// 判定函数：乘法表中 <= mid 的元素有多少个
int countLessEqual(int n, int m, int mid) {
    int count = 0;
    for (int i = 1; i <= n; i++) {
        // 第 i 行是 i, 2i, 3i, ..., mi
        // <= mid 的元素个数为 min(mid/i, m)
        count += min(mid / i, m);
    }
    return count;
}

// 二分答案：乘法表中第 k 小的数
int findKthNumber(int n, int m, int k) {
    int lo = 1, hi = n * m;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (countLessEqual(n, m, mid) >= k) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}

4.3 BFS 模板与最短路¶

4.3.1 BFS 基本原理¶

广度优先搜索（BFS）：从起点开始，按层次逐层向外扩展，第一次到达目标时的路径就是最短路径（在无权图中）。

graph TD
    A["起点入队"] --> B["取出队首"]
    B --> C["扩展所有未访问的邻居"]
    C --> D["邻居入队"]
    D --> B
    B --> E["队列为空 / 找到目标"]

4.3.2 BFS 模板¶

#include <bits/stdc++.h>
using namespace std;

// BFS 模板：网格最短路径
int bfs(vector<vector<int>>& grid, int sx, int sy, int ex, int ey) {
    int n = grid.size(), m = grid[0].size();
    int dx[] = {-1, 1, 0, 0};  // 方向数组：上下左右
    int dy[] = {0, 0, -1, 1};

    // visited 数组记录是否访问过
    vector<vector<bool>> visited(n, vector<bool>(m, false));
    queue<pair<int, int>> q;

    q.push({sx, sy});
    visited[sx][sy] = true;
    int steps = 0;

    while (!q.empty()) {
        int size = q.size();  // 当前层的节点数
        for (int i = 0; i < size; i++) {
            auto [x, y] = q.front();
            q.pop();

            if (x == ex && y == ey) return steps;  // 找到目标

            for (int d = 0; d < 4; d++) {
                int nx = x + dx[d];
                int ny = y + dy[d];
                // 检查边界、是否可走、是否已访问
                if (nx >= 0 && nx < n && ny >= 0 && ny < m &&
                    grid[nx][ny] == 0 && !visited[nx][ny]) {
                    visited[nx][ny] = true;
                    q.push({nx, ny});
                }
            }
        }
        steps++;  // 一层遍历完，步数 +1
    }
    return -1;  // 无法到达
}

4.3.3 网格 BFS¶

例题：最短路径（0-1 网格）

给定一个 n x m 的网格，0 表示可通行，1 表示障碍。求从左上角到右下角的最短路径长度。

#include <bits/stdc++.h>
using namespace std;

int shortestPath(vector<vector<int>>& grid) {
    int n = grid.size(), m = grid[0].size();
    if (grid[0][0] == 1 || grid[n-1][m-1] == 1) return -1;

    int dx[] = {-1, 1, 0, 0};
    int dy[] = {0, 0, -1, 1};

    vector<vector<int>> dist(n, vector<int>(m, -1));  // -1 表示未访问
    queue<pair<int, int>> q;

    q.push({0, 0});
    dist[0][0] = 1;  // 起点也算一步

    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();

        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d];
            int ny = y + dy[d];
            if (nx >= 0 && nx < n && ny >= 0 && ny < m &&
                grid[nx][ny] == 0 && dist[nx][ny] == -1) {
                dist[nx][ny] = dist[x][y] + 1;
                q.push({nx, ny});
            }
        }
    }
    return dist[n-1][m-1];
}

4.3.4 多源 BFS¶

问题：有多个起点同时出发，求每个点到最近起点的距离。

技巧：将所有起点同时入队，一起向外扩展。

#include <bits/stdc++.h>
using namespace std;

// 多源 BFS：多个起点同时出发
vector<vector<int>> multiSourceBFS(vector<vector<int>>& grid,
                                    vector<pair<int, int>>& sources) {
    int n = grid.size(), m = grid[0].size();
    int dx[] = {-1, 1, 0, 0};
    int dy[] = {0, 0, -1, 1};

    vector<vector<int>> dist(n, vector<int>(m, -1));
    queue<pair<int, int>> q;

    // 所有源点同时入队
    for (auto& [x, y] : sources) {
        q.push({x, y});
        dist[x][y] = 0;
    }

    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();

        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d];
            int ny = y + dy[d];
            if (nx >= 0 && nx < n && ny >= 0 && ny < m && dist[nx][ny] == -1) {
                dist[nx][ny] = dist[x][y] + 1;
                q.push({nx, ny});
            }
        }
    }
    return dist;
}

BFS 求最短路的条件

BFS 适用于无权图（或权值相同的图）的最短路径。如果边权不同，需要使用 Dijkstra 等算法。

4.3.5 拓展：0-1 BFS 与双向 BFS¶

0-1 BFS：当边权只有 0 和 1 两种时，不必上 Dijkstra——把普通队列换成双端队列即可：经 0 权边扩展出的点放队首（距离不变，相当于同层），经 1 权边扩展出的点放队尾（距离 +1，相当于下一层）。这样队列中的距离仍保持单调，复杂度 O(V + E)。

// 0-1 BFS：边权只有 0 和 1 的最短路，复杂度 O(V + E)
vector<int> zeroOneBFS(vector<vector<pair<int,int>>>& g, int s) {
    int n = g.size();
    vector<int> dist(n, INT_MAX);
    deque<int> dq;
    dist[s] = 0;
    dq.push_back(s);
    while (!dq.empty()) {
        int u = dq.front(); dq.pop_front();
        for (auto [v, w] : g[u]) {             // w 只能是 0 或 1
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                if (w == 0) dq.push_front(v);  // 0 权边：放队首，优先扩展
                else dq.push_back(v);          // 1 权边：放队尾
            }
        }
    }
    return dist;
}

双向 BFS：当起点和终点都已知时，可以从两端同时向中间搜索，每轮扩展节点数较少的一侧，两侧访问集合一旦相遇即得到最短路。设分支因子为 b、最短路长为 d，搜索量从 O(b^d) 降到 O(2·b^(d/2))，对状态空间巨大的问题（如单词接龙、八数码）提速非常明显。实现要点：用两个 visited 集合分别记录两端已访问状态，每轮把节点少的那侧整体扩展一层，扩展出的状态若出现在对侧集合中即可返回两侧步数之和。

4.4 DFS 模板与遍历¶

4.4.1 DFS 基本原理¶

深度优先搜索（DFS）：沿着一条路径一直走到底，然后回溯到上一个分叉点，尝试其他路径。

graph TD
    A["从起点开始"] --> B["选择一条未走过的路"]
    B --> C["走到下一个节点"]
    C --> D{"还有路可走?"}
    D -->|是| B
    D -->|否| E["回溯到上一个节点"]
    E --> D

4.4.2 DFS 模板（递归）¶

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005;
vector<int> graph[MAXN];  // 邻接表
bool visited[MAXN];

// DFS 模板
void dfs(int u) {
    visited[u] = true;
    // 处理当前节点 u

    for (int v : graph[u]) {
        if (!visited[v]) {
            dfs(v);  // 递归访问邻居
        }
    }
    // 回溯（如果需要恢复状态）
}

4.4.3 DFS 模板（迭代，使用栈）¶

#include <bits/stdc++.h>
using namespace std;

// DFS 迭代写法（用栈模拟递归）
void dfsIterative(vector<vector<int>>& graph, int start) {
    int n = graph.size();
    vector<bool> visited(n, false);
    stack<int> st;

    st.push(start);

    while (!st.empty()) {
        int u = st.top();
        st.pop();

        if (visited[u]) continue;
        visited[u] = true;

        // 处理节点 u

        // 注意：为了保持 DFS 顺序，邻居要逆序入栈
        for (int i = graph[u].size() - 1; i >= 0; i--) {
            int v = graph[u][i];
            if (!visited[v]) {
                st.push(v);
            }
        }
    }
}

4.4.4 DFS 应用：树的遍历¶

#include <bits/stdc++.h>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 前序遍历：根 -> 左 -> 右
void preorder(TreeNode* root) {
    if (!root) return;
    cout << root->val << " ";  // 访问根节点
    preorder(root->left);       // 遍历左子树
    preorder(root->right);      // 遍历右子树
}

// 中序遍历：左 -> 根 -> 右
void inorder(TreeNode* root) {
    if (!root) return;
    inorder(root->left);
    cout << root->val << " ";
    inorder(root->right);
}

// 后序遍历：左 -> 右 -> 根
void postorder(TreeNode* root) {
    if (!root) return;
    postorder(root->left);
    postorder(root->right);
    cout << root->val << " ";
}

4.5 Flood Fill（泛洪填充）¶

核心思想¶

从一个起始点出发，将所有与其连通且满足条件的点进行标记或修改。常用 DFS 或 BFS 实现。

graph LR
    A["选起点"] --> B["标记为已访问"]
    B --> C["向四个方向扩展"]
    C --> D{"邻居满足条件?"}
    D -->|是| E["递归填充邻居"]
    D -->|否| F["跳过"]
    E --> C

经典例题：图像渲染¶

问题：给定一个二维网格表示图像，一个起始坐标和新颜色，将起始坐标所在连通区域的颜色全部改为新颜色。

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int dx[4] = {-1, 1, 0, 0};
    int dy[4] = {0, 0, -1, 1};
    int n, m;
    int oldColor;

    // DFS 泛洪填充
    void dfs(vector<vector<int>>& image, int x, int y, int newColor) {
        // 边界检查 & 颜色检查
        if (x < 0 || x >= n || y < 0 || y >= m) return;
        if (image[x][y] != oldColor) return;

        image[x][y] = newColor;  // 修改颜色

        for (int d = 0; d < 4; d++) {
            dfs(image, x + dx[d], y + dy[d], newColor);
        }
    }

    vector<vector<int>> floodFill(vector<vector<int>>& image,
                                   int sr, int sc, int newColor) {
        n = image.size();
        m = image[0].size();
        oldColor = image[sr][sc];

        if (oldColor != newColor)  // 避免无限递归
            dfs(image, sr, sc, newColor);

        return image;
    }
};

BFS 写法¶

#include <bits/stdc++.h>
using namespace std;

// BFS 写法的泛洪填充
vector<vector<int>> floodFillBFS(vector<vector<int>>& image,
                                  int sr, int sc, int newColor) {
    int n = image.size(), m = image[0].size();
    int oldColor = image[sr][sc];
    if (oldColor == newColor) return image;

    int dx[] = {-1, 1, 0, 0};
    int dy[] = {0, 0, -1, 1};

    queue<pair<int, int>> q;
    q.push({sr, sc});
    image[sr][sc] = newColor;

    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();

        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d];
            int ny = y + dy[d];
            if (nx >= 0 && nx < n && ny >= 0 && ny < m &&
                image[nx][ny] == oldColor) {
                image[nx][ny] = newColor;
                q.push({nx, ny});
            }
        }
    }
    return image;
}

Flood Fill 应用场景¶

场景	说明
数岛屿	统计网格中连通的 `1` 的个数
染色	将连通区域涂上新颜色
迷宫求解	标记可达区域
游戏中的区域识别	如扫雷展开

4.6 剪枝技巧¶

什么是剪枝？¶

剪枝是指在搜索过程中，提前排除不可能产生最优解的分支，从而减少搜索空间。

graph TD
    A["搜索树"] --> B["可行剪枝: 排除不合法的分支"]
    A --> C["最优剪枝: 排除不能优于当前最优的分支"]
    B --> D["减少搜索量"]
    C --> D

4.6.1 可行性剪枝¶

在搜索过程中，如果当前路径已经不可能满足约束条件，直接回溯。

// 示例：N 皇后问题中的可行性剪枝
bool isValid(vector<int>& queens, int row, int col) {
    for (int i = 0; i < row; i++) {
        // 检查列冲突和对角线冲突
        if (queens[i] == col || abs(queens[i] - col) == abs(i - row))
            return false;
    }
    return true;
}

void solveNQueens(vector<int>& queens, int row, int n, int& count) {
    if (row == n) {
        count++;
        return;
    }
    for (int col = 0; col < n; col++) {
        if (!isValid(queens, row, col)) continue;  // 可行性剪枝
        queens[row] = col;
        solveNQueens(queens, row + 1, n, count);
    }
}

4.6.2 最优性剪枝¶

在搜索最优解的过程中，如果当前路径的代价已经超过已知最优解，直接回溯。

// 示例：TSP（旅行商问题）中的最优性剪枝
int bestDist = INT_MAX;  // 当前最优解

void tsp(vector<vector<int>>& dist, vector<bool>& visited,
         int u, int count, int n, int curDist) {
    // 最优性剪枝：当前距离已超过已知最优
    if (curDist >= bestDist) return;

    if (count == n) {
        bestDist = min(bestDist, curDist + dist[u][0]);  // 回到起点
        return;
    }

    for (int v = 0; v < n; v++) {
        if (!visited[v]) {
            visited[v] = true;
            tsp(dist, visited, v, count + 1, n, curDist + dist[u][v]);
            visited[v] = false;  // 回溯
        }
    }
}

4.6.3 重复性剪枝¶

避免搜索到相同的状态，使用 visited 数组或记忆化来去重。

4.6.4 搜索顺序优化¶

优先搜索"更有希望"的分支，可以更快找到最优解。

// 示例：在搜索前对候选节点排序（如贪心顺序）
sort(candidates.begin(), candidates.end(), [](const auto& a, const auto& b) {
    return a.estimated_cost < b.estimated_cost;  // 按估价排序
});

剪枝策略总结¶

剪枝类型	思路	应用场景
可行性剪枝	当前状态已违反约束	N 皇后、数独
最优性剪枝	当前代价已超过已知最优	TSP、最优化搜索
重复性剪枝	避免搜索相同状态	网格搜索、记忆化
搜索顺序优化	优先搜索更有希望的分支	组合搜索、IDA*

拓展：迭代加深与 IDA*

迭代加深搜索（IDDFS）：给 DFS 设一个深度上限 limit，从 limit = 1 开始逐次加 1 重新搜索。它用 DFS 的 O(深度) 空间获得了 BFS 的"按层找最短解"效果，适合"解的深度不深但状态分支很多"的问题。 IDA*：在迭代加深的基础上引入估价函数 h(状态)（乐观估计到目标还需的步数，不能高估），若"当前深度 + h > limit"直接剪枝，比裸 IDDFS 快得多。经典应用：八数码、十五数码、埃及分数。属于进阶内容，本书不展开完整例题，感兴趣可参考洛谷 P1379（八数码）与 UVA 1343。

4.7 三分搜索¶

4.7.1 核心思想¶

二分处理的是单调函数，三分处理的是单峰函数：函数在 [l, r] 上先严格递增、到达峰值后严格递减（求最小值时相反）。此时中点两侧无法用"大于/小于目标"来判断方向，改为取两个三等分点 m1 < m2 比较函数值：

若 f(m1) < f(m2)：峰值一定不在 [l, m1]，舍弃左段
若 f(m1) >= f(m2)：峰值一定不在 [m2, r]，舍弃右段

每轮把区间缩为原来的 2/3，复杂度 O(log((r-l)/ε))（每轮 2 次函数求值）。

graph LR
    A["单峰函数 [l, r]"] --> B["取三等分点 m1, m2"]
    B --> C{"f(m1) < f(m2)?"}
    C -->|是| D["峰在 (m1, r]，令 l = m1"]
    C -->|否| E["峰在 [l, m2)，令 r = m2"]
    D --> B
    E --> B

4.7.2 整数三分模板¶

// 整数三分：f 在 [l, r] 上严格单峰（先增后减），求最大值点
long long ternarySearch(long long l, long long r) {
    while (r - l > 2) {                    // 区间缩到长度 <= 3 时停止
        long long m1 = l + (r - l) / 3;
        long long m2 = r - (r - l) / 3;
        if (f(m1) < f(m2)) l = m1 + 1;     // 峰一定在 (m1, r]
        else r = m2 - 1;                    // 峰一定在 [l, m2)
    }
    long long best = l;                     // 剩余小区间直接暴力
    for (long long i = l + 1; i <= r; i++)
        if (f(i) > f(best)) best = i;
    return best;
}

整数三分的另一种写法

严格单峰（无相邻相等值）时也可以二分"上坡/下坡"：比较 f(mid) 与 f(mid + 1)，若 f(mid) < f(mid + 1) 说明 mid 在上坡段，l = mid + 1；否则 r = mid。循环到 l == r 即为峰值点，每轮只求值 2 次且代码更短。

4.7.3 浮点三分模板¶

// 浮点三分：求单峰函数 f 在 [l, r] 上的最大值点
double ternarySearchReal(double l, double r) {
    while (r - l > 1e-7) {          // 精度按题目要求调整，也可固定循环 200 次
        double m1 = l + (r - l) / 3;
        double m2 = r - (r - l) / 3;
        if (f(m1) < f(m2)) l = m1;
        else r = m2;
    }
    return l;
}

4.7.4 例题：洛谷 P3382 【模板】三分¶

题意：给出一个 N 次函数（以系数形式给出，N ≤ 13）以及区间 [l, r]，保证函数在 [l, r] 内单峰（先增后减），求峰值点 x（误差不超过 10^-5）。

#include <bits/stdc++.h>
using namespace std;

int n;
double c[15];  // 多项式系数（从最高次到常数项）

// 秦九韶算法求 f(x)
double f(double x) {
    double res = 0;
    for (int i = 0; i <= n; i++) res = res * x + c[i];
    return res;
}

int main() {
    double l, r;
    cin >> n >> l >> r;
    for (int i = 0; i <= n; i++) cin >> c[i];

    while (r - l > 1e-7) {              // 浮点三分：区间每轮缩为 2/3
        double m1 = l + (r - l) / 3;
        double m2 = r - (r - l) / 3;
        if (f(m1) < f(m2)) l = m1;      // 极大值点在 [m1, r]
        else r = m2;                     // 极大值点在 [l, m2]
    }
    printf("%.5f\n", l);
    return 0;
}

复杂度分析：每轮区间缩为 2/3，共 O(log((r-l)/ε)) 轮，每轮求值 2 次，单次求值 O(N)。

三分的常见坑

必须严格单峰：函数若有"平台段"（一段相等的值），f(m1) == f(m2) 时无法判断峰在哪一侧，三分会出错
求最小值时把比较方向反过来（或对 -f 求最大值）
整数三分收尾时区间还剩 2 ~ 3 个点，要暴力扫一遍取最值，不能直接返回 l
浮点三分不要用 l != r 作为循环条件，会死循环；用精度差或固定循环次数

4.8 折半搜索（Meet in the Middle）¶

4.8.1 核心思想¶

当 n ≈ 40 时，直接枚举全部 2^40 ≈ 10^12 个子集不可行，但 2^20 ≈ 10^6 完全可以接受。折半搜索把元素分成两半分别枚举，再把两半的结果合并：

\[ 2^{40} \;\longrightarrow\; 2 \times 2^{20} + \text{合并代价} \]

graph TD
    A["n 个元素（n ≈ 40）"] --> B["前一半：枚举 2^(n/2) 个子集"]
    A --> C["后一半：枚举 2^(n/2) 个子集"]
    B --> D["合并：排序 + 二分 / 双指针"]
    C --> D
    D --> E["总复杂度 O(2^(n/2) · n)"]

合并的常见手段：对一半的结果排序，另一半逐个二分查找（或两半都排序后双指针扫描）。

4.8.2 例题：洛谷 P4799 [CEOI2015 Day2] 世界冰球锦标赛¶

题意：有 n 场比赛（n ≤ 40），第 i 场票价为 a_i，预算为 M（0 ≤ M ≤ 10^18）。求有多少种观赛方案（子集，可以为空），使得总花费不超过 M。

思路：分成前后两半分别枚举所有子集和；对后一半的子集和排序，对前一半的每个和 s，用 upper_bound 统计后一半中和 ≤ M - s 的个数并累加。

#include <bits/stdc++.h>
using namespace std;

int n;
long long m, a[45];
vector<long long> sumL, sumR;

// 枚举下标区间 [l, r] 内所有子集的和，存入 res
void enumerateHalf(int l, int r, vector<long long>& res) {
    int len = r - l + 1;
    for (int s = 0; s < (1 << len); s++) {
        long long sum = 0;
        for (int i = 0; i < len; i++)
            if (s >> i & 1) sum += a[l + i];
        res.push_back(sum);
    }
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> a[i];

    int mid = n / 2;
    enumerateHalf(0, mid - 1, sumL);   // 前一半：2^(n/2) 个子集和
    enumerateHalf(mid, n - 1, sumR);   // 后一半
    sort(sumR.begin(), sumR.end());    // 对一半排序，另一半逐个二分

    long long ans = 0;
    for (long long s : sumL) {
        if (s > m) continue;
        // 右半部分中和 <= m - s 的子集个数
        ans += upper_bound(sumR.begin(), sumR.end(), m - s) - sumR.begin();
    }
    cout << ans << endl;
    return 0;
}

样例：n=5, M=1000，票价 {100, 1500, 500, 500, 1000}，输出 8（含空集）。

复杂度分析：枚举两半 O(2^(n/2) · n/2)，排序 O(2^(n/2) · n/2)，合并 O(2^(n/2) · n/2)，总计 O(2^(n/2) · n)；空间 O(2^(n/2))。

折半搜索的常见坑

答案会爆 int：方案数最多 2^40，必须用 long long；子集和也可能超出 int 范围
枚举子集时 1 << len 在 len ≥ 31 时溢出，分半后 len ≤ 20 才安全——这正是"必须折半"的原因之一
空集（和为 0）通常也算一种方案，两半的枚举都要从 s = 0 开始
合并方式取决于问题：计数用排序 + 二分/双指针，求最接近某值用 lower_bound，判存在性用哈希表

综合例题¶

例题 1：单词接龙（BFS）¶

问题：给定两个单词 beginWord 和 endWord，以及一个字典，每次只能变换一个字母，求从 beginWord 到 endWord 的最短转换序列长度。

#include <bits/stdc++.h>
using namespace std;

int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
    unordered_set<string> dict(wordList.begin(), wordList.end());
    if (!dict.count(endWord)) return 0;

    queue<string> q;
    q.push(beginWord);
    unordered_set<string> visited;
    visited.insert(beginWord);
    int steps = 1;

    while (!q.empty()) {
        int size = q.size();
        for (int i = 0; i < size; i++) {
            string word = q.front();
            q.pop();

            // 尝试修改每个字符
            for (int j = 0; j < word.size(); j++) {
                char original = word[j];
                for (char c = 'a'; c <= 'z'; c++) {
                    word[j] = c;
                    if (word == endWord) return steps + 1;
                    if (dict.count(word) && !visited.count(word)) {
                        visited.insert(word);
                        q.push(word);
                    }
                }
                word[j] = original;  // 恢复
            }
        }
        steps++;
    }
    return 0;
}

例题 2：岛屿数量（DFS / Flood Fill）¶

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int dx[4] = {-1, 1, 0, 0};
    int dy[4] = {0, 0, -1, 1};

    void dfs(vector<vector<char>>& grid, int x, int y) {
        int n = grid.size(), m = grid[0].size();
        if (x < 0 || x >= n || y < 0 || y >= m || grid[x][y] != '1')
            return;

        grid[x][y] = '0';  // 标记为已访问（沉岛）

        for (int d = 0; d < 4; d++)
            dfs(grid, x + dx[d], y + dy[d]);
    }

    int numIslands(vector<vector<char>>& grid) {
        int n = grid.size(), m = grid[0].size();
        int count = 0;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == '1') {
                    count++;
                    dfs(grid, i, j);  // 沉掉整个岛屿
                }
            }
        }
        return count;
    }
};

练习题¶

LeetCode 暑假 - DFS & BFS¶

题号	题目	难度	链接	完成
100	Same Tree	Easy	链接	- [ ]
104	Maximum Depth of Binary Tree	Easy	链接	- [ ]
101	Symmetric Tree	Easy	链接	- [ ]
897	Increasing Order Search Tree	Easy	链接	- [ ]
938	Range Sum of BST	Easy	链接	- [ ]
997	Find the Town Judge	Easy	链接	- [ ]
463	Island Perimeter	Easy	链接	- [ ]
733	Flood Fill	Easy	链接	- [ ]
441	Arranging Coins	Easy	链接	- [ ]
1022	Sum of Root To Leaf Binary Numbers	Easy	链接	- [ ]
69	Sqrt(x)	Easy	链接	- [ ]
399	Evaluate Division	Medium	链接	- [ ]
529	Minesweeper	Medium	链接	- [ ]
419	Battleships in a Board	Medium	链接	- [ ]
107	Binary Tree Level Order Traversal II	Medium	链接	- [ ]
130	Surrounded Regions	Medium	链接	- [ ]
1026	Maximum Difference Between Node and Ancestor	Medium	链接	- [ ]
756	Pyramid Transition Matrix	Medium	链接	- [ ]
378	Kth Smallest Element in a Sorted Matrix	Medium	链接	- [ ]
611	Valid Triangle Number	Medium	链接	- [ ]
2616	Minimize the Maximum Difference of Pairs	Medium	链接	- [ ]
126	Word Ladder II	Hard	链接	- [ ]
127	Word Ladder	Hard	链接	- [ ]
301	Remove Invalid Parentheses	Hard	链接	- [ ]
407	Trapping Rain Water II	Hard	链接	- [ ]
668	Kth Smallest Number in Multiplication Table	Hard	链接	- [ ]
410	Split Array Largest Sum	Hard	链接	- [ ]
753	Cracking the Safe	Hard	链接	- [ ]
297	Serialize and Deserialize Binary Tree	Hard	链接	- [ ]
4	Median of Two Sorted Arrays	Hard	链接	- [ ]

参考解答¶

以下给出上表中已整理的参考题解，按 Easy / Hard 分组（题号与上表一一对应；Easy 组 10 题，Hard 组 9 题）。建议先独立完成，再展开折叠块对照。

题号	平台	题目	难度	链接	完成
1907D	CF	Jumping Through Segments	1400	链接	- [ ]
1985F	CF	Final Boss	1500	链接	- [ ]
1971E	CF	Find the Car	1500	链接	- [ ]
2009E	CF	Klee's SUPER DUPER LARGE Array!!!	1400	链接	- [ ]

题号	题目	难度	链接	完成
374	Guess Number Higher or Lower	Easy	链接	- [ ]
349	Intersection of Two Arrays	Easy	链接	- [ ]
190	Reverse Bits	Easy	链接	- [ ]
191	Number of 1 Bits	Easy	链接	- [ ]
200	Number of Islands	Medium	链接	- [ ]
543	Diameter of Binary Tree	Easy	链接	- [ ]

第四章 搜索与二分¶

4.1 二分查找原理与实现¶

4.1.1 二分查找的基本思想¶

4.1.2 整数二分¶

模板一：寻找左边界（满足条件的最小值）¶

模板二：寻找右边界（满足条件的最大值）¶

完整示例：查找元素的起始和结束位置¶

4.1.3 浮点二分¶

4.1.4 STL 二分函数¶

4.2 二分答案（判定性问题）¶

核心思想¶

经典模型¶

模型一：最小化最大值¶

模型二：最大化最小值¶

模型三：满足条件的第 k 小/大¶

4.3 BFS 模板与最短路¶

4.3.1 BFS 基本原理¶

4.3.2 BFS 模板¶

4.3.3 网格 BFS¶

4.3.4 多源 BFS¶

4.3.5 拓展：0-1 BFS 与双向 BFS¶

4.4 DFS 模板与遍历¶

4.4.1 DFS 基本原理¶

4.4.2 DFS 模板（递归）¶

4.4.3 DFS 模板（迭代，使用栈）¶

4.4.4 DFS 应用：树的遍历¶

4.5 Flood Fill（泛洪填充）¶

核心思想¶

经典例题：图像渲染¶

BFS 写法¶

Flood Fill 应用场景¶

4.6 剪枝技巧¶

什么是剪枝？¶

4.6.1 可行性剪枝¶

4.6.2 最优性剪枝¶

4.6.3 重复性剪枝¶

4.6.4 搜索顺序优化¶

剪枝策略总结¶

4.7 三分搜索¶

4.7.1 核心思想¶

4.7.2 整数三分模板¶

4.7.3 浮点三分模板¶

4.7.4 例题：洛谷 P3382 【模板】三分¶

4.8 折半搜索（Meet in the Middle）¶

4.8.1 核心思想¶

4.8.2 例题：洛谷 P4799 [CEOI2015 Day2] 世界冰球锦标赛¶

综合例题¶

例题 1：单词接龙（BFS）¶

例题 2：岛屿数量（DFS / Flood Fill）¶

练习题¶

LeetCode 暑假 - DFS & BFS¶

参考解答¶

Easy 组¶

LC 733. Flood Fill¶

LC 463. Island Perimeter¶

LC 69. Sqrt(x)¶

LC 441. Arranging Coins¶

LC 1022. Sum of Root To Leaf Binary Numbers¶

LC 897. Increasing Order Search Tree¶

LC 100. Same Tree¶

LC 104. Maximum Depth of Binary Tree¶

LC 101. Symmetric Tree¶

LC 997. Find the Town Judge¶

Hard 组¶

LC 126. Word Ladder II¶

LC 127. Word Ladder¶

LC 301. Remove Invalid Parentheses¶

LC 407. Trapping Rain Water II¶

LC 668. Kth Smallest Number in Multiplication Table¶

LC 410. Split Array Largest Sum¶

LC 753. Cracking the Safe¶

LC 297. Serialize and Deserialize Binary Tree¶

LC 4. Median of Two Sorted Arrays¶

ACM Day1 - 二分部分¶

寒假二分 / 搜索¶

本章小结¶

第四章搜索与二分¶