← 数据结构与算法（共 12 章） 🗺️ 学习路线

第 3 章　数组、字符串与二分查找

red wenzi · 2026-09-20 · 计算机基础 · 数据结构与算法 · 📖 预计阅读 32 分钟 · 四语言对照 · 代码实测编译运行
🎯 本章你会学到：数组为什么随机访问 O(1)、插入删除却要 O(n)；前缀和怎么把区间求和降到 O(1)；差分数组怎么把区间批量修改降到 O(1)；二分查找三种写法的边界差别；以及二分答案这个从「找一个数」升级到「找一个最优解」的套路。

数组是笔试里出现频率最高的结构，理由很直接：它简单、能随机访问、缓存友好。但只用「一个循环扫一遍」不够——这一章要教的是怎么用预处理把查询变快。

两段程序都是四语言对照，代码在 gcc 16.1 / g++ 16.1 / javac 21 / Python 3.14 下实测编译运行，四份输出逐字节一致。

3.1 数组：连续内存换来了什么

数组把元素放在一整块连续内存里，并且每个元素一样大。这两点合起来，让「第 k 个元素在哪」变成一道算术题：

第 k 个元素的地址 = 起始地址 + k × 单个元素大小

不用找、不用数，一次乘加就算出来了，所以随机访问是 O(1)。这也是为什么数组下标从 0 开始——偏移量直接就是 k。

连续内存还带来一个隐形好处：缓存友好。CPU 读内存是一小块一小块读的，连续访问时下一份数据很可能已经在缓存里了，所以「数组顺序遍历」通常比「链表跳着遍历」快好几倍，哪怕两者复杂度一样（第 1 章提过这一点）。

3.2 数组的代价：插入和删除为什么要搬家

既然元素是紧挨着排的，那在中间插一个元素，就必须把它后面的元素全部往后挪一格，否则就重叠了。删除同理，要往前填补空位。

本章程序一实测（n = 1000）的移动次数：

操作实测移动元素数复杂度原因
随机访问第 500 个1 次取值O(1)直接算地址
尾部追加（容量够）0O(1)直接放到末尾
头部插入1000O(n)所有元素右移一格
尾部插入（触发扩容）1001（拷贝）O(n)换一块更大的内存，整体搬过去
删除头部1001O(n)后面所有元素左移一格
删除尾部0O(1)把长度减一就行
📌 一句话记住：数组「读得快、两端快、中间慢」。凡是要在数组中间频繁增删的场景，就该考虑链表或别的结构（第 1 章）；而在尾部增删（push_back / append）因为有均摊分析兜着，仍然是 O(1)（第 2 章）。

3.3 字符串：本质是字符数组

字符串在底层就是「一串字符」，只是四门语言对它的处理差别很大，写题时必须知道：

语言类型可变吗按下标访问拼接 n 次的代价
Cchar[] + 结尾的 '\0'可变O(1)手动管理长度，容易溢出，建议用 snprintf
C++std::string可变O(1)会按倍数扩容，均摊 O(n)
JavaString不可变O(1)每次拼接都造新对象，O(n²)，必须用 StringBuilder
Pythonstr不可变O(1)（索引）同样 O(n²)，要用 "".join(list)

三条容易踩的结论：

⚠️ 字符串进阶算法（KMP、Manacher、后缀数组）在本章不展开：它们属于「面试低频、性价比一般」的内容，先把数组上的前缀和、差分、二分、双指针练熟更划算。想了解可以查 知识大全。

3.4 程序一：数组代价、前缀和、差分（四语言对照）

这段程序用固定种子的伪随机数生成 1000 个数据，然后实测四件事：数组四种操作的移动次数、前缀和的预处理与查询代价、差分数组的修改与还原代价。

C

array_cost.c
/* =====================================================================
   数据结构与算法 · 第 3 章 数组、字符串与二分查找 · 数组代价实测（C）
   编译运行： gcc -std=c17 -Wall -Wextra -o app array_cost.c && ./app

   本章要回答三个问题：
     ① 数组的「随机访问快、中间插入慢」到底体现在哪？——数元素移动次数；
     ② 区间求和为什么能做到 O(1)？——前缀和，预处理 O(n)、查询 O(1)；
     ③ 区间批量加为什么也能做到 O(1)？——差分数组，修改 O(1)、还原 O(n)。

   复杂度（时间 / 空间）
     随机访问 O(1) / O(1)
     尾部追加（容量够）O(1) / O(1)      头部插入 / 删除 O(n) / O(1)
     前缀和：预处理 O(n) / O(n)          区间查询 O(1) / O(1)
     差分：区间加 O(1) / O(n)            还原 O(n) / O(1)
   ===================================================================== */

#include <stdio.h>

#define N 1000
#define L 200
#define R 800

static int data[N];
static int buf[N + 2];          /* 留两格余量：头部插入 1 个 + 尾部插入 1 个 */
static long prefix[N + 1];      /* prefix[i] = data[0..i) 的和 */
static long diff[N + 1];

/* 固定种子的伪随机数列：与第 2 章同一个种子，方便对照 */
static void lcg_fill(int *a, int n) {
    unsigned long long x = 12345ULL;
    for (int i = 0; i < n; ++i) {
        x = (x * 1103515245ULL + 12345ULL) % 2147483648ULL;
        a[i] = (int)(x % 2000ULL);
    }
}

int main(void) {
    lcg_fill(data, N);

    /* ---- ① 数组的四种基本操作的代价 ---- */
    int random_access = data[N / 2];                 /* 随机访问：1 次取值 */

    for (int i = 0; i < N; ++i) buf[i] = data[i];    /* 复制一份来演示插入删除 */
    int size = N;

    int tail_appended = data[N - 1];                 /* 尾部追加（容量够）：不移动元素 */

    /* 头部插入：先把 1000 个元素整体右移一格 */
    long head_insert_moves = 0;
    for (int i = size; i > 0; --i) { buf[i] = buf[i - 1]; head_insert_moves++; }
    buf[0] = 42;
    size++;

    /* 尾部插入（需要扩容）：先把已有元素整体搬到新数组 */
    long tail_insert_moves = 0;
    for (int i = 0; i < size; ++i) tail_insert_moves++;   /* 扩容时要拷贝的元素个数 */
    buf[size] = 43;
    size++;

    /* 删除头部：把后面 999 个元素整体左移一格 */
    long head_delete_moves = 0;
    for (int i = 0; i + 1 < size; ++i) { buf[i] = buf[i + 1]; head_delete_moves++; }
    size--;

    int tail_deleted_moves = 0;                      /* 删除尾部：不移动元素 */
    size--;

    /* ---- ② 前缀和：预处理一次，之后每次区间求和都是 O(1) ---- */
    long prefix_adds = 0;
    prefix[0] = 0;
    for (int i = 0; i < N; ++i) { prefix[i + 1] = prefix[i] + data[i]; prefix_adds++; }

    long range_sum_fast = prefix[R] - prefix[L];      /* 1 次减法 */
    long range_sum_brute = 0;
    long brute_adds = 0;
    for (int i = L; i < R; ++i) { range_sum_brute += data[i]; brute_adds++; }

    /* ---- ③ 差分数组：区间批量加只需改两个位置 ---- */
    for (int i = 0; i <= N; ++i) diff[i] = 0;
    diff[L] += 5;
    diff[R] -= 5;
    long diff_changes = 2;

    long restore_adds = 0;
    long cur = 0;
    long restored_range_sum = 0;
    for (int i = 0; i < N; ++i) {
        cur += diff[i];
        restore_adds++;
        if (i >= L && i < R) restored_range_sum += data[i] + cur;
    }

    printf("[数组] 数据规模 n = %d\n", N);
    printf("[数组] 随机访问第 %d 个: %d（1 次取值）, O(1)\n", N / 2, random_access);
    printf("[数组] 尾部追加（容量够）: 移动 0 个元素（读到 %d）, O(1)\n", tail_appended);
    printf("[数组] 头部插入: 移动 %ld 个元素, O(n)\n", head_insert_moves);
    printf("[数组] 尾部插入（触发扩容）: 拷贝 %ld 个元素, O(n)\n", tail_insert_moves);
    printf("[数组] 删除头部: 移动 %ld 个元素, O(n)\n", head_delete_moves);
    printf("[数组] 删除尾部: 移动 %d 个元素, O(1)\n", tail_deleted_moves);
    printf("[前缀和] 预处理 %d 个元素: %ld 次加法, O(n)\n", N, prefix_adds);
    printf("[前缀和] 区间 [%d, %d) 求和: 1 次减法 = %ld, O(1)\n", L, R, range_sum_fast);
    printf("[前缀和] 同区间暴力求和: %ld 次加法 = %ld, O(n)\n", brute_adds, range_sum_brute);
    printf("[前缀和] 两者结果一致: %s\n", range_sum_fast == range_sum_brute ? "是" : "否");
    printf("[差分] 区间 [%d, %d) 批量加 5: %ld 次修改, O(1)\n", L, R, diff_changes);
    printf("[差分] 从差分数组还原: %ld 次加法, O(n)\n", restore_adds);
    printf("[差分] 还原后该区间和 = %ld（原区间和 %ld + %d×5）\n",
           restored_range_sum, range_sum_brute, R - L);
    return 0;
}

C++

array_cost.cpp
// =====================================================================
// 数据结构与算法 · 第 3 章 数组、字符串与二分查找 · 数组代价实测（C++）
// 编译运行： g++ -std=c++17 -Wall -Wextra -Wpedantic -o app array_cost.cpp && ./app
//
// 复杂度（时间 / 空间）
//   随机访问 O(1) / O(1)            尾部追加（容量够）O(1) / O(1)
//   头部插入 / 删除 O(n) / O(1)     前缀和：预处理 O(n)、查询 O(1)
//   差分：区间加 O(1)、还原 O(n)
// =====================================================================

#include <cstdio>

constexpr int N = 1000;
constexpr int L = 200;
constexpr int R = 800;

int data_[N];
int buf[N + 2];              // 留两格余量：头部插入 1 个 + 尾部插入 1 个
long prefix[N + 1];          // prefix[i] = data[0..i) 的和
long diff[N + 1];

// 固定种子的伪随机数列：与第 2 章同一个种子，方便对照
void lcg_fill(int *a, int n) {
    unsigned long long x = 12345ULL;
    for (int i = 0; i < n; ++i) {
        x = (x * 1103515245ULL + 12345ULL) % 2147483648ULL;
        a[i] = static_cast<int>(x % 2000ULL);
    }
}

int main() {
    lcg_fill(data_, N);

    int random_access = data_[N / 2];                 // 随机访问：1 次取值

    for (int i = 0; i < N; ++i) buf[i] = data_[i];
    int size = N;

    int tail_appended = data_[N - 1];                 // 尾部追加（容量够）：不移动元素

    long head_insert_moves = 0;                       // 头部插入：整体右移
    for (int i = size; i > 0; --i) { buf[i] = buf[i - 1]; ++head_insert_moves; }
    buf[0] = 42;
    ++size;

    long tail_insert_moves = 0;                       // 尾部插入触发扩容：整体拷贝
    for (int i = 0; i < size; ++i) ++tail_insert_moves;
    buf[size] = 43;
    ++size;

    long head_delete_moves = 0;                       // 删除头部：整体左移
    for (int i = 0; i + 1 < size; ++i) { buf[i] = buf[i + 1]; ++head_delete_moves; }
    --size;

    int tail_deleted_moves = 0;                       // 删除尾部：不移动元素
    --size;

    long prefix_adds = 0;
    prefix[0] = 0;
    for (int i = 0; i < N; ++i) { prefix[i + 1] = prefix[i] + data_[i]; ++prefix_adds; }

    long range_sum_fast = prefix[R] - prefix[L];
    long range_sum_brute = 0;
    long brute_adds = 0;
    for (int i = L; i < R; ++i) { range_sum_brute += data_[i]; ++brute_adds; }

    for (int i = 0; i <= N; ++i) diff[i] = 0;
    diff[L] += 5;
    diff[R] -= 5;
    long diff_changes = 2;

    long restore_adds = 0;
    long cur = 0;
    long restored_range_sum = 0;
    for (int i = 0; i < N; ++i) {
        cur += diff[i];
        ++restore_adds;
        if (i >= L && i < R) restored_range_sum += data_[i] + cur;
    }

    std::printf("[数组] 数据规模 n = %d\n", N);
    std::printf("[数组] 随机访问第 %d 个: %d（1 次取值）, O(1)\n", N / 2, random_access);
    std::printf("[数组] 尾部追加（容量够）: 移动 0 个元素（读到 %d）, O(1)\n", tail_appended);
    std::printf("[数组] 头部插入: 移动 %ld 个元素, O(n)\n", head_insert_moves);
    std::printf("[数组] 尾部插入（触发扩容）: 拷贝 %ld 个元素, O(n)\n", tail_insert_moves);
    std::printf("[数组] 删除头部: 移动 %ld 个元素, O(n)\n", head_delete_moves);
    std::printf("[数组] 删除尾部: 移动 %d 个元素, O(1)\n", tail_deleted_moves);
    std::printf("[前缀和] 预处理 %d 个元素: %ld 次加法, O(n)\n", N, prefix_adds);
    std::printf("[前缀和] 区间 [%d, %d) 求和: 1 次减法 = %ld, O(1)\n", L, R, range_sum_fast);
    std::printf("[前缀和] 同区间暴力求和: %ld 次加法 = %ld, O(n)\n", brute_adds, range_sum_brute);
    std::printf("[前缀和] 两者结果一致: %s\n", range_sum_fast == range_sum_brute ? "是" : "否");
    std::printf("[差分] 区间 [%d, %d) 批量加 5: %ld 次修改, O(1)\n", L, R, diff_changes);
    std::printf("[差分] 从差分数组还原: %ld 次加法, O(n)\n", restore_adds);
    std::printf("[差分] 还原后该区间和 = %ld（原区间和 %ld + %d×5）\n",
                restored_range_sum, range_sum_brute, R - L);
    return 0;
}

Java

ArrayCost.java
// =====================================================================
// 数据结构与算法 · 第 3 章 数组、字符串与二分查找 · 数组代价实测（Java）
// 编译运行： javac -encoding UTF-8 ArrayCost.java
//            java -Dstdout.encoding=UTF-8 ArrayCost
//
// 复杂度（时间 / 空间）
//   随机访问 O(1) / O(1)            尾部追加（容量够）O(1) / O(1)
//   头部插入 / 删除 O(n) / O(1)     前缀和：预处理 O(n)、查询 O(1)
//   差分：区间加 O(1)、还原 O(n)
// =====================================================================

public class ArrayCost {

    static final int N = 1000;
    static final int L = 200;
    static final int R = 800;

    static int[] data = new int[N];
    static int[] buf = new int[N + 2];      // 留两格余量：头部插入 1 个 + 尾部插入 1 个
    static long[] prefix = new long[N + 1]; // prefix[i] = data[0..i) 的和
    static long[] diff = new long[N + 1];

    // 固定种子的伪随机数列：与第 2 章同一个种子，方便对照
    static void lcgFill(int[] a, int n) {
        long x = 12345L;
        for (int i = 0; i < n; ++i) {
            x = (x * 1103515245L + 12345L) % 2147483648L;
            a[i] = (int) (x % 2000L);
        }
    }

    public static void main(String[] args) {
        lcgFill(data, N);

        int randomAccess = data[N / 2];                 // 随机访问：1 次取值

        for (int i = 0; i < N; ++i) buf[i] = data[i];
        int size = N;

        int tailAppended = data[N - 1];                 // 尾部追加（容量够）

        long headInsertMoves = 0;                       // 头部插入：整体右移
        for (int i = size; i > 0; --i) { buf[i] = buf[i - 1]; ++headInsertMoves; }
        buf[0] = 42;
        ++size;

        long tailInsertMoves = 0;                       // 尾部插入触发扩容：整体拷贝
        for (int i = 0; i < size; ++i) ++tailInsertMoves;
        buf[size] = 43;
        ++size;

        long headDeleteMoves = 0;                       // 删除头部：整体左移
        for (int i = 0; i + 1 < size; ++i) { buf[i] = buf[i + 1]; ++headDeleteMoves; }
        --size;

        int tailDeletedMoves = 0;                       // 删除尾部
        --size;

        long prefixAdds = 0;
        prefix[0] = 0;
        for (int i = 0; i < N; ++i) { prefix[i + 1] = prefix[i] + data[i]; ++prefixAdds; }

        long rangeSumFast = prefix[R] - prefix[L];
        long rangeSumBrute = 0;
        long bruteAdds = 0;
        for (int i = L; i < R; ++i) { rangeSumBrute += data[i]; ++bruteAdds; }

        for (int i = 0; i <= N; ++i) diff[i] = 0;
        diff[L] += 5;
        diff[R] -= 5;
        long diffChanges = 2;

        long restoreAdds = 0;
        long cur = 0;
        long restoredRangeSum = 0;
        for (int i = 0; i < N; ++i) {
            cur += diff[i];
            ++restoreAdds;
            if (i >= L && i < R) restoredRangeSum += data[i] + cur;
        }

        System.out.println("[数组] 数据规模 n = " + N);
        System.out.println("[数组] 随机访问第 " + (N / 2) + " 个: " + randomAccess + "（1 次取值）, O(1)");
        System.out.println("[数组] 尾部追加（容量够）: 移动 0 个元素（读到 " + tailAppended + "）, O(1)");
        System.out.println("[数组] 头部插入: 移动 " + headInsertMoves + " 个元素, O(n)");
        System.out.println("[数组] 尾部插入（触发扩容）: 拷贝 " + tailInsertMoves + " 个元素, O(n)");
        System.out.println("[数组] 删除头部: 移动 " + headDeleteMoves + " 个元素, O(n)");
        System.out.println("[数组] 删除尾部: 移动 " + tailDeletedMoves + " 个元素, O(1)");
        System.out.println("[前缀和] 预处理 " + N + " 个元素: " + prefixAdds + " 次加法, O(n)");
        System.out.println("[前缀和] 区间 [" + L + ", " + R + ") 求和: 1 次减法 = " + rangeSumFast + ", O(1)");
        System.out.println("[前缀和] 同区间暴力求和: " + bruteAdds + " 次加法 = " + rangeSumBrute + ", O(n)");
        System.out.println("[前缀和] 两者结果一致: " + (rangeSumFast == rangeSumBrute ? "是" : "否"));
        System.out.println("[差分] 区间 [" + L + ", " + R + ") 批量加 5: " + diffChanges + " 次修改, O(1)");
        System.out.println("[差分] 从差分数组还原: " + restoreAdds + " 次加法, O(n)");
        System.out.println("[差分] 还原后该区间和 = " + restoredRangeSum
                + "（原区间和 " + rangeSumBrute + " + " + (R - L) + "×5）");
    }
}

Python

array_cost.py
# =====================================================================
# 数据结构与算法 · 第 3 章 数组、字符串与二分查找 · 数组代价实测（Python）
# 运行： python array_cost.py
#
# 复杂度（时间 / 空间）
#   随机访问 O(1) / O(1)            尾部追加（容量够）O(1) / O(1)
#   头部插入 / 删除 O(n) / O(1)     前缀和：预处理 O(n)、查询 O(1)
#   差分：区间加 O(1)、还原 O(n)
# =====================================================================

N = 1000
L = 200
R = 800


def lcg_fill(a, n):
    """固定种子的伪随机数列：与第 2 章同一个种子，方便对照"""
    x = 12345
    for i in range(n):
        x = (x * 1103515245 + 12345) % 2147483648
        a[i] = x % 2000


def main():
    data = [0] * N
    lcg_fill(data, N)

    random_access = data[N // 2]                 # 随机访问：1 次取值

    buf = data[:] + [0, 0]                       # 留两格余量：头部插入 1 个 + 尾部插入 1 个
    size = N

    tail_appended = data[N - 1]                  # 尾部追加（容量够）：不移动元素

    head_insert_moves = 0                        # 头部插入：整体右移
    for i in range(size, 0, -1):
        buf[i] = buf[i - 1]
        head_insert_moves += 1
    buf[0] = 42
    size += 1

    tail_insert_moves = 0                        # 尾部插入触发扩容：整体拷贝
    for i in range(size):
        tail_insert_moves += 1
    buf[size] = 43
    size += 1

    head_delete_moves = 0                        # 删除头部：整体左移
    for i in range(size - 1):
        buf[i] = buf[i + 1]
        head_delete_moves += 1
    size -= 1

    tail_deleted_moves = 0                       # 删除尾部：不移动元素
    size -= 1

    prefix = [0] * (N + 1)                       # 前缀和：预处理一次
    prefix_adds = 0
    for i in range(N):
        prefix[i + 1] = prefix[i] + data[i]
        prefix_adds += 1

    range_sum_fast = prefix[R] - prefix[L]       # 1 次减法
    range_sum_brute = 0
    brute_adds = 0
    for i in range(L, R):
        range_sum_brute += data[i]
        brute_adds += 1

    diff = [0] * (N + 1)                         # 差分数组：区间加
    diff[L] += 5
    diff[R] -= 5
    diff_changes = 2

    restore_adds = 0
    cur = 0
    restored_range_sum = 0
    for i in range(N):
        cur += diff[i]
        restore_adds += 1
        if L <= i < R:
            restored_range_sum += data[i] + cur

    print("[数组] 数据规模 n = %d" % N)
    print("[数组] 随机访问第 %d 个: %d（1 次取值）, O(1)" % (N // 2, random_access))
    print("[数组] 尾部追加（容量够）: 移动 0 个元素（读到 %d）, O(1)" % tail_appended)
    print("[数组] 头部插入: 移动 %d 个元素, O(n)" % head_insert_moves)
    print("[数组] 尾部插入（触发扩容）: 拷贝 %d 个元素, O(n)" % tail_insert_moves)
    print("[数组] 删除头部: 移动 %d 个元素, O(n)" % head_delete_moves)
    print("[数组] 删除尾部: 移动 %d 个元素, O(1)" % tail_deleted_moves)
    print("[前缀和] 预处理 %d 个元素: %d 次加法, O(n)" % (N, prefix_adds))
    print("[前缀和] 区间 [%d, %d) 求和: 1 次减法 = %d, O(1)" % (L, R, range_sum_fast))
    print("[前缀和] 同区间暴力求和: %d 次加法 = %d, O(n)" % (brute_adds, range_sum_brute))
    print("[前缀和] 两者结果一致: %s" % ("是" if range_sum_fast == range_sum_brute else "否"))
    print("[差分] 区间 [%d, %d) 批量加 5: %d 次修改, O(1)" % (L, R, diff_changes))
    print("[差分] 从差分数组还原: %d 次加法, O(n)" % restore_adds)
    print("[差分] 还原后该区间和 = %d（原区间和 %d + %d×5）"
          % (restored_range_sum, range_sum_brute, R - L))


if __name__ == "__main__":
    main()

实测输出（四份逐字节一致）

运行结果
[数组] 数据规模 n = 1000
[数组] 随机访问第 500 个: 1194（1 次取值）, O(1)
[数组] 尾部追加（容量够）: 移动 0 个元素（读到 65）, O(1)
[数组] 头部插入: 移动 1000 个元素, O(n)
[数组] 尾部插入（触发扩容）: 拷贝 1001 个元素, O(n)
[数组] 删除头部: 移动 1001 个元素, O(n)
[数组] 删除尾部: 移动 0 个元素, O(1)
[前缀和] 预处理 1000 个元素: 1000 次加法, O(n)
[前缀和] 区间 [200, 800) 求和: 1 次减法 = 595380, O(1)
[前缀和] 同区间暴力求和: 600 次加法 = 595380, O(n)
[前缀和] 两者结果一致: 是
[差分] 区间 [200, 800) 批量加 5: 2 次修改, O(1)
[差分] 从差分数组还原: 1000 次加法, O(n)
[差分] 还原后该区间和 = 598380（原区间和 595380 + 600×5）
🔍 从输出里能读出三件事：
① 头部插入要移动 1000 个元素、删除头部要移动 1001 个，而尾部的两个操作都是 0——这就是「两端快、中间慢」；
② 区间 [200, 800) 求和：前缀和 1 次减法，暴力求和 600 次加法，结果都是 595380。预处理花 1000 次加法，之后每次查询都省下 599 次；
③ 差分数组把「600 个元素各加 5」变成 2 次修改，代价转移到一次 O(n) 的还原上——这就是「空间换时间」的另一种形态：把代价从「每次查询」挪到「最后汇总一次」。

3.5 前缀和：一次预处理，换来无数次 O(1) 查询

要反复求「数组区间 [L, R) 的和」，直觉是每次循环加一遍，那是 O(n)。前缀和把它变成 O(1)：

prefix[0] = 0
prefix[i + 1] = prefix[i] + a[i]        # 预处理 O(n)
区间 [L, R) 的和 = prefix[R] - prefix[L]   # 查询 O(1)

为什么成立？因为 prefix[R] 是「前 R 个元素的和」，prefix[L] 是「前 L 个元素的和」，两者相减，剩下的正好是 [L, R) 这一段。

二维前缀和：矩形区域求和

矩阵里求「左上角 (0,0) 到 (i,j) 这块矩形的和」也用同样思路，靠容斥原理拼出来：

S[i+1][j+1] = S[i][j+1] + S[i+1][j] - S[i][j] + a[i][j]
区域 (r1,c1) 到 (r2,c2) 的和 = S[r2+1][c2+1] - S[r1][c2+1] - S[r2+1][c1] + S[r1][c1]

预处理 O(nm)、每次查询 O(1)。减掉重复加的部分、再加回被减两次的部分，就是容斥。

📌 什么时候用前缀和：数组不变、但要被反复问「某一段的和」时。如果数组频繁修改，前缀和每次都要重建 O(n)，这时候要么用差分，要么用线段树 / 树状数组。

3.6 差分数组：把「区间批量加」变成 O(1)

反过来的问题是：要给区间 [L, R) 里的每个元素都加 v，做很多次，最后才输出整个数组。暴力每次都要改 R-L 个元素，O(n)。

差分数组把它变成 O(1)：只在两个位置动手，最后一次性还原。

diff[L] += v          # 从 L 开始，之后都多加了 v
diff[R] -= v          # 从 R 开始，把多加的 v 抵消掉
# 还原：cur 一路累加 diff，a[i] + cur 就是修改后的值
cur = 0
for i in 0..n-1:
    cur += diff[i]
    result[i] = a[i] + cur

本章实测：区间 [200, 800) 批量加 5，只做了 2 次修改；还原时做 1000 次加法。还原后该区间和从 595380 变成 598380，正好多了 600 × 5 = 3000。

做法每次区间加最后输出适合场景
暴力O(n)O(1)只要改一两次
差分数组O(1)O(n)要改很多次、最后统一输出

3.7 程序二：二分查找的三种写法（四语言对照）

二分查找思路谁都懂（每次砍一半），但边界写错是面试挂人的常客。三种写法都要能默写：

C

binary_search.c
/* =====================================================================
   数据结构与算法 · 第 3 章 数组、字符串与二分查找 · 二分查找（C）
   编译运行： gcc -std=c17 -Wall -Wextra -o app binary_search.c && ./app

   三种写法都要会，因为边界处理不同，面试最爱在这里挑错：
     ① 闭区间 [lo, hi]    —— hi 取 n-1，循环条件 lo <= hi
     ② 左闭右开 [lo, hi)  —— hi 取 n，循环条件 lo < hi
     ③ lower_bound        —— 找「第一个 >= target」的位置，不存在时返回应插入位置

   复杂度（时间 / 空间）
     二分查找 O(log n) / O(1)
     二分答案 O(log(答案范围) × 判定代价) / O(1)
   ===================================================================== */

#include <stdio.h>

#define N 1000

static int a[N];

/* ① 闭区间 [lo, hi]：hi 取 n-1 */
static int bsearch_closed(const int *arr, int n, int target, long *cmp) {
    int lo = 0, hi = n - 1;
    while (lo <= hi) {
        (*cmp)++;
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] == target) return mid;
        if (arr[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

/* ② 左闭右开 [lo, hi)：hi 取 n */
static int bsearch_half_open(const int *arr, int n, int target, long *cmp) {
    int lo = 0, hi = n;
    while (lo < hi) {
        (*cmp)++;
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] == target) return mid;
        if (arr[mid] < target) lo = mid + 1;
        else hi = mid;
    }
    return -1;
}

/* ③ lower_bound：第一个 >= target 的下标（可能返回 n，表示比所有元素都大） */
static int lower_bound_idx(const int *arr, int n, int target, long *cmp) {
    int lo = 0, hi = n;
    while (lo < hi) {
        (*cmp)++;
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] < target) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}

/* 二分答案：假设每段长 len，能切出多少段 */
static long cut_count(const int *wood, int k, int len) {
    long seg = 0;
    for (int i = 0; i < k; ++i) seg += wood[i] / len;
    return seg;
}

/* 二分答案：求最大的等长 L，使切出的段数 >= need */
static int max_cut_length(const int *wood, int k, long need, long *checks) {
    int lo = 1, hi = 0;
    for (int i = 0; i < k; ++i) if (wood[i] > hi) hi = wood[i];
    int ans = 0;
    while (lo <= hi) {
        (*checks)++;
        int mid = lo + (hi - lo) / 2;
        if (cut_count(wood, k, mid) >= need) { ans = mid; lo = mid + 1; }
        else hi = mid - 1;
    }
    return ans;
}

int main(void) {
    for (int i = 0; i < N; ++i) a[i] = i * 3;      /* 有序：0, 3, 6, ... 2997 */

    long cmp1 = 0, cmp2 = 0, cmp3 = 0, cmp4 = 0;
    int i1 = bsearch_closed(a, N, 1800, &cmp1);
    int i2 = bsearch_half_open(a, N, 1800, &cmp2);
    int i3 = lower_bound_idx(a, N, 1800, &cmp3);
    int i4 = lower_bound_idx(a, N, 1801, &cmp4);

    /* 边界用例：空数组、单元素、第一个、最后一个、不存在 */
    int empty[1] = {0};
    int one[1] = {5};
    long tmp = 0;
    int e1 = bsearch_closed(empty, 0, 5, &tmp);
    int e2 = bsearch_closed(one, 1, 5, &tmp);
    int e3 = bsearch_closed(one, 1, 9, &tmp);
    int e4 = bsearch_closed(a, N, 0, &tmp);
    int e5 = bsearch_closed(a, N, 2997, &tmp);
    int e6 = bsearch_closed(a, N, 1801, &tmp);

    /* 二分答案：把木头切成至少 7 段，求最大等长 */
    int wood[3] = {10, 24, 16};
    long checks = 0;
    int best = max_cut_length(wood, 3, 7, &checks);

    printf("[二分] 有序数组 n = %d（a[i] = i × 3）\n", N);
    printf("[二分] 闭区间 [lo, hi]    找 1800: 找到, 下标 %d, 比较 %ld 次\n", i1, cmp1);
    printf("[二分] 左闭右开 [lo, hi)  找 1800: 找到, 下标 %d, 比较 %ld 次\n", i2, cmp2);
    printf("[二分] lower_bound 找 1800: 下标 %d, 比较 %ld 次\n", i3, cmp3);
    printf("[二分] lower_bound 找 1801: 下标 %d, 比较 %ld 次\n", i4, cmp4);
    printf("[二分] 边界用例:\n");
    printf("[二分]   空数组找 5: 返回 %d\n", e1);
    printf("[二分]   单元素 [5] 找 5: 返回 %d\n", e2);
    printf("[二分]   单元素 [5] 找 9: 返回 %d\n", e3);
    printf("[二分]   找第一个元素 0: 返回 %d\n", e4);
    printf("[二分]   找最后一个元素 2997: 返回 %d\n", e5);
    printf("[二分]   找不存在的 1801: 返回 %d\n", e6);
    printf("[二分答案] 切木头: 长度 [10, 24, 16]，要切成至少 7 段等长\n");
    printf("[二分答案] 最大等长 = %d, 判定 %ld 次\n", best, checks);
    printf("[二分答案] 验证: L=6 得 %ld 段（够），L=7 得 %ld 段（不够）\n",
           cut_count(wood, 3, 6), cut_count(wood, 3, 7));
    return 0;
}

C++

binary_search.cpp
// =====================================================================
// 数据结构与算法 · 第 3 章 数组、字符串与二分查找 · 二分查找（C++）
// 编译运行： g++ -std=c++17 -Wall -Wextra -Wpedantic -o app binary_search.cpp && ./app
//
// 三种写法都要会，因为边界处理不同，面试最爱在这里挑错：
//   ① 闭区间 [lo, hi]    ② 左闭右开 [lo, hi)    ③ lower_bound
//
// 复杂度（时间 / 空间）
//   二分查找 O(log n) / O(1)      二分答案 O(log(答案范围) × 判定代价) / O(1)
// =====================================================================

#include <cstdio>

constexpr int N = 1000;

int a[N];

// ① 闭区间 [lo, hi]：hi 取 n-1
int bsearch_closed(const int *arr, int n, int target, long *cmp) {
    int lo = 0, hi = n - 1;
    while (lo <= hi) {
        ++(*cmp);
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] == target) return mid;
        if (arr[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

// ② 左闭右开 [lo, hi)：hi 取 n
int bsearch_half_open(const int *arr, int n, int target, long *cmp) {
    int lo = 0, hi = n;
    while (lo < hi) {
        ++(*cmp);
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] == target) return mid;
        if (arr[mid] < target) lo = mid + 1;
        else hi = mid;
    }
    return -1;
}

// ③ lower_bound：第一个 >= target 的下标（可能返回 n）
int lower_bound_idx(const int *arr, int n, int target, long *cmp) {
    int lo = 0, hi = n;
    while (lo < hi) {
        ++(*cmp);
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] < target) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}

// 二分答案：假设每段长 len，能切出多少段
long cut_count(const int *wood, int k, int len) {
    long seg = 0;
    for (int i = 0; i < k; ++i) seg += wood[i] / len;
    return seg;
}

// 二分答案：求最大的等长 L，使切出的段数 >= need
int max_cut_length(const int *wood, int k, long need, long *checks) {
    int lo = 1, hi = 0;
    for (int i = 0; i < k; ++i) if (wood[i] > hi) hi = wood[i];
    int ans = 0;
    while (lo <= hi) {
        ++(*checks);
        int mid = lo + (hi - lo) / 2;
        if (cut_count(wood, k, mid) >= need) { ans = mid; lo = mid + 1; }
        else hi = mid - 1;
    }
    return ans;
}

int main() {
    for (int i = 0; i < N; ++i) a[i] = i * 3;      // 有序：0, 3, 6, ... 2997

    long cmp1 = 0, cmp2 = 0, cmp3 = 0, cmp4 = 0;
    int i1 = bsearch_closed(a, N, 1800, &cmp1);
    int i2 = bsearch_half_open(a, N, 1800, &cmp2);
    int i3 = lower_bound_idx(a, N, 1800, &cmp3);
    int i4 = lower_bound_idx(a, N, 1801, &cmp4);

    int empty[1] = {0};
    int one[1] = {5};
    long tmp = 0;
    int e1 = bsearch_closed(empty, 0, 5, &tmp);
    int e2 = bsearch_closed(one, 1, 5, &tmp);
    int e3 = bsearch_closed(one, 1, 9, &tmp);
    int e4 = bsearch_closed(a, N, 0, &tmp);
    int e5 = bsearch_closed(a, N, 2997, &tmp);
    int e6 = bsearch_closed(a, N, 1801, &tmp);

    int wood[3] = {10, 24, 16};
    long checks = 0;
    int best = max_cut_length(wood, 3, 7, &checks);

    std::printf("[二分] 有序数组 n = %d（a[i] = i × 3）\n", N);
    std::printf("[二分] 闭区间 [lo, hi]    找 1800: 找到, 下标 %d, 比较 %ld 次\n", i1, cmp1);
    std::printf("[二分] 左闭右开 [lo, hi)  找 1800: 找到, 下标 %d, 比较 %ld 次\n", i2, cmp2);
    std::printf("[二分] lower_bound 找 1800: 下标 %d, 比较 %ld 次\n", i3, cmp3);
    std::printf("[二分] lower_bound 找 1801: 下标 %d, 比较 %ld 次\n", i4, cmp4);
    std::printf("[二分] 边界用例:\n");
    std::printf("[二分]   空数组找 5: 返回 %d\n", e1);
    std::printf("[二分]   单元素 [5] 找 5: 返回 %d\n", e2);
    std::printf("[二分]   单元素 [5] 找 9: 返回 %d\n", e3);
    std::printf("[二分]   找第一个元素 0: 返回 %d\n", e4);
    std::printf("[二分]   找最后一个元素 2997: 返回 %d\n", e5);
    std::printf("[二分]   找不存在的 1801: 返回 %d\n", e6);
    std::printf("[二分答案] 切木头: 长度 [10, 24, 16]，要切成至少 7 段等长\n");
    std::printf("[二分答案] 最大等长 = %d, 判定 %ld 次\n", best, checks);
    std::printf("[二分答案] 验证: L=6 得 %ld 段（够），L=7 得 %ld 段（不够）\n",
                cut_count(wood, 3, 6), cut_count(wood, 3, 7));
    return 0;
}

Java

BinarySearch.java
// =====================================================================
// 数据结构与算法 · 第 3 章 数组、字符串与二分查找 · 二分查找（Java）
// 编译运行： javac -encoding UTF-8 BinarySearch.java
//            java -Dstdout.encoding=UTF-8 BinarySearch
//
// 三种写法都要会，因为边界处理不同，面试最爱在这里挑错：
//   ① 闭区间 [lo, hi]    ② 左闭右开 [lo, hi)    ③ lower_bound
//
// 复杂度（时间 / 空间）
//   二分查找 O(log n) / O(1)      二分答案 O(log(答案范围) × 判定代价) / O(1)
// =====================================================================

public class BinarySearch {

    static final int N = 1000;
    static int[] a = new int[N];
    static long cmp = 0;      // 用一个字段累计比较次数，方便在 main 里清零复用

    // ① 闭区间 [lo, hi]：hi 取 n-1
    static int bsearchClosed(int[] arr, int n, int target) {
        int lo = 0, hi = n - 1;
        while (lo <= hi) {
            ++cmp;
            int mid = lo + (hi - lo) / 2;
            if (arr[mid] == target) return mid;
            if (arr[mid] < target) lo = mid + 1;
            else hi = mid - 1;
        }
        return -1;
    }

    // ② 左闭右开 [lo, hi)：hi 取 n
    static int bsearchHalfOpen(int[] arr, int n, int target) {
        int lo = 0, hi = n;
        while (lo < hi) {
            ++cmp;
            int mid = lo + (hi - lo) / 2;
            if (arr[mid] == target) return mid;
            if (arr[mid] < target) lo = mid + 1;
            else hi = mid;
        }
        return -1;
    }

    // ③ lower_bound：第一个 >= target 的下标（可能返回 n）
    static int lowerBoundIdx(int[] arr, int n, int target) {
        int lo = 0, hi = n;
        while (lo < hi) {
            ++cmp;
            int mid = lo + (hi - lo) / 2;
            if (arr[mid] < target) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    }

    // 二分答案：假设每段长 len，能切出多少段
    static long cutCount(int[] wood, int k, int len) {
        long seg = 0;
        for (int i = 0; i < k; ++i) seg += wood[i] / len;
        return seg;
    }

    // 二分答案：求最大的等长 L，使切出的段数 >= need
    static int maxCutLength(int[] wood, int k, long need, long[] checks) {
        int lo = 1, hi = 0;
        for (int i = 0; i < k; ++i) if (wood[i] > hi) hi = wood[i];
        int ans = 0;
        while (lo <= hi) {
            ++checks[0];
            int mid = lo + (hi - lo) / 2;
            if (cutCount(wood, k, mid) >= need) { ans = mid; lo = mid + 1; }
            else hi = mid - 1;
        }
        return ans;
    }

    public static void main(String[] args) {
        for (int i = 0; i < N; ++i) a[i] = i * 3;      // 有序：0, 3, 6, ... 2997

        cmp = 0;
        int i1 = bsearchClosed(a, N, 1800);
        long cmp1 = cmp;
        cmp = 0;
        int i2 = bsearchHalfOpen(a, N, 1800);
        long cmp2 = cmp;
        cmp = 0;
        int i3 = lowerBoundIdx(a, N, 1800);
        long cmp3 = cmp;
        cmp = 0;
        int i4 = lowerBoundIdx(a, N, 1801);
        long cmp4 = cmp;

        int[] empty = {0};
        int[] one = {5};
        int e1 = bsearchClosed(empty, 0, 5);
        int e2 = bsearchClosed(one, 1, 5);
        int e3 = bsearchClosed(one, 1, 9);
        int e4 = bsearchClosed(a, N, 0);
        int e5 = bsearchClosed(a, N, 2997);
        int e6 = bsearchClosed(a, N, 1801);

        int[] wood = {10, 24, 16};
        long[] checks = {0};
        int best = maxCutLength(wood, 3, 7, checks);

        System.out.println("[二分] 有序数组 n = " + N + "（a[i] = i × 3）");
        System.out.println("[二分] 闭区间 [lo, hi]    找 1800: 找到, 下标 " + i1 + ", 比较 " + cmp1 + " 次");
        System.out.println("[二分] 左闭右开 [lo, hi)  找 1800: 找到, 下标 " + i2 + ", 比较 " + cmp2 + " 次");
        System.out.println("[二分] lower_bound 找 1800: 下标 " + i3 + ", 比较 " + cmp3 + " 次");
        System.out.println("[二分] lower_bound 找 1801: 下标 " + i4 + ", 比较 " + cmp4 + " 次");
        System.out.println("[二分] 边界用例:");
        System.out.println("[二分]   空数组找 5: 返回 " + e1);
        System.out.println("[二分]   单元素 [5] 找 5: 返回 " + e2);
        System.out.println("[二分]   单元素 [5] 找 9: 返回 " + e3);
        System.out.println("[二分]   找第一个元素 0: 返回 " + e4);
        System.out.println("[二分]   找最后一个元素 2997: 返回 " + e5);
        System.out.println("[二分]   找不存在的 1801: 返回 " + e6);
        System.out.println("[二分答案] 切木头: 长度 [10, 24, 16]，要切成至少 7 段等长");
        System.out.println("[二分答案] 最大等长 = " + best + ", 判定 " + checks[0] + " 次");
        System.out.println("[二分答案] 验证: L=6 得 " + cutCount(wood, 3, 6)
                + " 段（够），L=7 得 " + cutCount(wood, 3, 7) + " 段（不够）");
    }
}

Python

binary_search.py
# =====================================================================
# 数据结构与算法 · 第 3 章 数组、字符串与二分查找 · 二分查找（Python）
# 运行： python binary_search.py
#
# 三种写法都要会，因为边界处理不同，面试最爱在这里挑错：
#   ① 闭区间 [lo, hi]    ② 左闭右开 [lo, hi)    ③ lower_bound
#
# 复杂度（时间 / 空间）
#   二分查找 O(log n) / O(1)      二分答案 O(log(答案范围) × 判定代价) / O(1)
# =====================================================================

N = 1000


def bsearch_closed(arr, n, target):
    """① 闭区间 [lo, hi]：hi 取 n-1，返回 (下标, 比较次数)"""
    lo, hi, cmp_count = 0, n - 1, 0
    while lo <= hi:
        cmp_count += 1
        mid = lo + (hi - lo) // 2
        if arr[mid] == target:
            return mid, cmp_count
        if arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1, cmp_count


def bsearch_half_open(arr, n, target):
    """② 左闭右开 [lo, hi)：hi 取 n，返回 (下标, 比较次数)"""
    lo, hi, cmp_count = 0, n, 0
    while lo < hi:
        cmp_count += 1
        mid = lo + (hi - lo) // 2
        if arr[mid] == target:
            return mid, cmp_count
        if arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return -1, cmp_count


def lower_bound_idx(arr, n, target):
    """③ 第一个 >= target 的下标（可能返回 n），返回 (下标, 比较次数)"""
    lo, hi, cmp_count = 0, n, 0
    while lo < hi:
        cmp_count += 1
        mid = lo + (hi - lo) // 2
        if arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo, cmp_count


def cut_count(wood, k, length):
    """二分答案：假设每段长 length，能切出多少段"""
    seg = 0
    for i in range(k):
        seg += wood[i] // length
    return seg


def max_cut_length(wood, k, need):
    """二分答案：求最大的等长 L，使切出的段数 >= need，返回 (L, 判定次数)"""
    lo, hi = 1, max(wood[:k])
    ans, checks = 0, 0
    while lo <= hi:
        checks += 1
        mid = lo + (hi - lo) // 2
        if cut_count(wood, k, mid) >= need:
            ans = mid
            lo = mid + 1
        else:
            hi = mid - 1
    return ans, checks


def main():
    a = [i * 3 for i in range(N)]      # 有序：0, 3, 6, ... 2997

    i1, cmp1 = bsearch_closed(a, N, 1800)
    i2, cmp2 = bsearch_half_open(a, N, 1800)
    i3, cmp3 = lower_bound_idx(a, N, 1800)
    i4, cmp4 = lower_bound_idx(a, N, 1801)

    empty = [0]
    one = [5]
    e1, _ = bsearch_closed(empty, 0, 5)
    e2, _ = bsearch_closed(one, 1, 5)
    e3, _ = bsearch_closed(one, 1, 9)
    e4, _ = bsearch_closed(a, N, 0)
    e5, _ = bsearch_closed(a, N, 2997)
    e6, _ = bsearch_closed(a, N, 1801)

    wood = [10, 24, 16]
    best, checks = max_cut_length(wood, 3, 7)

    print("[二分] 有序数组 n = %d（a[i] = i × 3）" % N)
    print("[二分] 闭区间 [lo, hi]    找 1800: 找到, 下标 %d, 比较 %d 次" % (i1, cmp1))
    print("[二分] 左闭右开 [lo, hi)  找 1800: 找到, 下标 %d, 比较 %d 次" % (i2, cmp2))
    print("[二分] lower_bound 找 1800: 下标 %d, 比较 %d 次" % (i3, cmp3))
    print("[二分] lower_bound 找 1801: 下标 %d, 比较 %d 次" % (i4, cmp4))
    print("[二分] 边界用例:")
    print("[二分]   空数组找 5: 返回 %d" % e1)
    print("[二分]   单元素 [5] 找 5: 返回 %d" % e2)
    print("[二分]   单元素 [5] 找 9: 返回 %d" % e3)
    print("[二分]   找第一个元素 0: 返回 %d" % e4)
    print("[二分]   找最后一个元素 2997: 返回 %d" % e5)
    print("[二分]   找不存在的 1801: 返回 %d" % e6)
    print("[二分答案] 切木头: 长度 [10, 24, 16]，要切成至少 7 段等长")
    print("[二分答案] 最大等长 = %d, 判定 %d 次" % (best, checks))
    print("[二分答案] 验证: L=6 得 %d 段（够），L=7 得 %d 段（不够）"
          % (cut_count(wood, 3, 6), cut_count(wood, 3, 7)))


if __name__ == "__main__":
    main()

实测输出（四份逐字节一致）

运行结果
[二分] 有序数组 n = 1000（a[i] = i × 3）
[二分] 闭区间 [lo, hi]    找 1800: 找到, 下标 600, 比较 7 次
[二分] 左闭右开 [lo, hi)  找 1800: 找到, 下标 600, 比较 9 次
[二分] lower_bound 找 1800: 下标 600, 比较 10 次
[二分] lower_bound 找 1801: 下标 601, 比较 10 次
[二分] 边界用例:
[二分]   空数组找 5: 返回 -1
[二分]   单元素 [5] 找 5: 返回 0
[二分]   单元素 [5] 找 9: 返回 -1
[二分]   找第一个元素 0: 返回 0
[二分]   找最后一个元素 2997: 返回 999
[二分]   找不存在的 1801: 返回 -1
[二分答案] 切木头: 长度 [10, 24, 16]，要切成至少 7 段等长
[二分答案] 最大等长 = 6, 判定 4 次
[二分答案] 验证: L=6 得 7 段（够），L=7 得 6 段（不够）
🔍 输出里最值得看的两点：
① 同样找 1800（在下标 600），闭区间写法比较 7 次、左闭右开写法比较 9 次。差别来自 mid 的取法（(999-0)/2 vs (1000-0)/2），不是谁写错了——但这也说明「二分的比较次数和具体写法有关」，别拿次数当正确性标准，要用边界用例验证；
② 六个边界用例全部正确：空数组返回 -1、单元素命中返回 0、单元素不命中返回 -1、找首元素返回 0、找末元素返回 999、找不存在的 1801 返回 -1。二分写对的分水岭就是这些用例能不能全过。

三种写法的差别，一张表说清

写法初始区间循环条件缩右边界时适合什么
闭区间lo=0, hi=n-1lo <= hihi = mid - 1新手最好记：区间两端都是闭的，mid 一定被排除在下一轮之外
左闭右开lo=0, hi=nlo < hihi = mid和 STL 的迭代器习惯一致，写「找边界」类题目更顺
lower_boundlo=0, hi=nlo < hihi = mid求「第一个 ≥ x 的位置」，是很多题目的核心动作
⚠️ 三条铁律，写二分时背下来：
① mid 一定写成 lo + (hi - lo) / 2，不要写 (lo + hi) / 2——后者在 lo、hi 都很大时会整型溢出；
② 缩边界时要么排除 mid、要么保证区间变小，否则会死循环（lo = mid 且 hi = mid + 1 这种就要小心）；
③ 数组必须有序。乱序数组上二分得到的不是「找不到」，而是随机答案。

3.8 二分答案：从「找一个数」到「找一个最优解」

这是二分里最值钱的套路。题目长这样：求满足某个条件的最大值 / 最小值，而「条件」随着你猜的答案单调变化。

本章的例子：有三根木头长度 10、24、16，要切成至少 7 段等长的，问每段最长能多长。

程序实测结果：最大等长 = 6，只做了 4 次判定。而如果从 1 枚举到 24，要判定 24 次。

lo = 1, hi = 最大木头长度, ans = 0
while lo <= hi:
    mid = lo + (hi - lo) / 2
    if 判定(mid) 可行:  ans = mid; lo = mid + 1     # 可行就往更大试
    else:               hi = mid - 1                # 不可行就往更小试
题目特征二分答案的判定函数怎么写例子
「最小化最大值」给定上界 X，判断能不能在 X 之内完成分割数组、运货问题、安排任务
「最大化最小值」给定下界 X，判断能不能达到 X切木头、分糖果、放牛问题
「找第 k 小 / 第 k 大」数一数 ≤ X 的有几个，和 k 比较有序矩阵第 k 小、乘法表第 k 小
📌 判断能不能用二分答案，只需问一句：当我猜的答案变大时，「可行」会不会从 true 变成 false（或者反过来）并且不再变回来？是，就能二分。

3.9 选型速查：这题该用哪个

题目特征该用什么复杂度
反复问某一段的和（数组不变）前缀和预处理 O(n)，每次查询 O(1)
反复对某一段整体加/减（最后才输出）差分数组每次修改 O(1)，最后还原 O(n)
在有序数组里找某个值 / 找边界二分查找O(log n)
求「最大化的最小值」「最小化的最大值」二分答案O(log(范围) × 判定代价)
求「最长/最短满足条件的连续子段」滑动窗口（第 4 章）O(n)
数组频繁单点修改 + 频繁区间查询树状数组 / 线段树（第 12 章）O(log n)

3.10 常见误区

误区正确说法
二分写在乱序数组上也能用不能。乱序时 mid 和 target 的大小关系不能说明 target 在哪半边，结果无意义
mid = (lo + hi) / 2 没问题lo、hi 接近 int 上限时会溢出。统一写 lo + (hi - lo) / 2
二分只有「找值」一种用法它的本质是「在单调序列上定位」：找边界、找答案、找第 k 小，都是二分
前缀和只能求一维二维也能，靠容斥原理，预处理 O(nm)、查询 O(1)
差分只能做加法减法同理；二维差分也能做矩形区域的批量修改
循环里用 += 拼字符串没关系Java / Python 字符串不可变，每次拼接都是新对象，O(n²)。用 StringBuilder / join
Python 切片 s[1:] 很便宜它会复制一份，是 O(长度)。循环里切片会把 O(n) 变成 O(n²)

3.11 运行命令（照抄就能跑）

语言文件命令
Carray_cost.c / binary_search.cgcc -std=c17 -Wall -Wextra -o app array_cost.c && ./app
C++array_cost.cpp / binary_search.cppg++ -std=c++17 -Wall -Wextra -Wpedantic -o app binary_search.cpp && ./app
JavaArrayCost.java / BinarySearch.javajavac -encoding UTF-8 BinarySearch.java 然后 java -Dstdout.encoding=UTF-8 BinarySearch
Pythonarray_cost.py / binary_search.pypython binary_search.py
⚙️ Windows 终端中文乱码时：先 chcp 65001；Python 另设 set PYTHONIOENCODING=utf-8；Java 用上面的 -Dstdout.encoding=UTF-8。macOS / Linux 把 ./app.exe 换成 ./app。

3.12 练习

3.1手推前缀和

数组 [3, 1, 4, 1, 5, 9, 2, 6]，写出它的前缀和数组（长度为 9，prefix[0] = 0），然后用它求出区间 [2, 6) 的和，再用暴力法核对一次。

提示：prefix = [0, 3, 4, 8, 9, 14, 23, 25, 31]；区间 [2,6) 的和 = prefix[6] - prefix[2]。
3.2把差分用起来

一个长度 10 的全 0 数组，依次执行：区间 [1, 4) 加 3、区间 [3, 8) 加 5、区间 [0, 3) 减 2。请只用差分数组记录（不改原数组），最后还原并写出结果数组。

提示：diff 上做 3 组「左端 +v、右端 -v」，最后前缀累加还原。
3.3三种二分都写一遍

在不看本章代码的前提下，用你熟悉的语言写出闭区间、左闭右开、lower_bound 三种二分，然后跑本章的六个边界用例，全部通过才算对。

提示：最容易错的是「空数组」和「找最后一个元素」两个用例。
3.4二分答案：分割数组

给定非负数组和目标段数 k，把它切成 k 段连续子数组，使「各段和的最大值」最小。写出判定函数 can(limit)，并用二分答案求出最小值。

提示：判定函数用贪心——从左往右累加，超过 limit 就切一段，看最后需要几段。
3.5改一段代码验证复杂度

把本章程序一的区间宽度从 [200, 800) 改成 [0, 1000) 和 [500, 501)，观察「差分修改次数」与「前缀和查询次数」有没有变化，并解释为什么。

提示：前缀和查询永远是 1 次减法、差分修改永远是 2 次，与区间长度无关——这正是它们存在的意义。
📚 本文概念都在知识大全：

时间复杂度 · vector · 前缀和 · 二分查找 · C 字符串 · Java 字符串 · Python 字符串

一句话回顾：数组随机访问 O(1)、中间增删 O(n)；前缀和把区间查询降到 O(1)，差分把区间修改降到 O(1)，两者都是「预处理换查询」；二分查找要默写三种写法并过边界用例；二分答案则是把「猜答案 + 单调性判定」用在最优化问题上——这套套路从第 4 章开始天天用。