二分法 | 王心俊老师信息学奥赛课件

模块 01

情景导航

从"猜数字"游戏开始，直觉理解二分的威力。

故事猜数字游戏：最多7次猜中1~100

老师在纸上写了一个 1~100 之间的整数，让小明来猜。每次猜完老师会告诉"大了"或"小了"。

笨办法：从1开始一个个猜，最坏要猜 100次。

聪明办法：每次都猜中间的数！

第1次：猜 50 → 老师说"大了"
第2次：猜 25 → 老师说"小了"
第3次：猜 37 → 老师说"大了"
第4次：猜 31 → 老师说"小了"
第5次：猜 34 → 老师说"对了"！🎉

只用了 5 次！最多也只要 7 次！

为什么？因为每次猜中间的数，搜索范围缩小一半：

100 → 50 → 25 → 13 → 7 → 4 → 2 → 1

最多 ⌈log₂(100)⌉ = 7 次就能确定答案！

这就是二分法 —— 每次排除一半，对数级效率！

💡 二分法 vs 线性查找

线性查找（一个个找）：n=10⁹ 时最坏要 10亿次 → 超时！

二分查找（每次砍半）：n=10⁹ 时最多 30次 → 瞬间完成！

10亿 vs 30，差距是 3300万倍！这就是 O(n) 和 O(log n) 的天壤之别。

①生活类比：二分无处不在

📖

翻字典

翻到中间看，大了往前翻，小了往后翻。

→ 二分查找

🔧

排查电路故障

从中间断开，看哪半段有问题，再对半段继续。

→ 二分定位

🎯

调音量

太大调小、太小调大，每次调到中间值。

→ 实数二分

📏

量体温

36°太低38°太高，试试37° → 逼近真实值。

→ 二分逼近

②编程定义

二分法（Binary Search）：在一个有序的搜索空间中，每次取中间值进行判断，从而将搜索范围缩小一半，直到找到目标或搜索空间为空。

核心前提：单调性 — 搜索空间必须满足某种单调性质（有序数组、单调函数等）。

时间复杂度：O(log n) — 每步将范围减半，最多 log₂n 步即可确定答案。

📌 本讲核心知识地图

板块	核心内容	对应大纲
二分查找	在有序数组中查找目标值	二分法
三大模板	标准二分 / lower_bound / upper_bound	二分法
二分答案	二分"答案"，用 check() 验证	二分法应用
实数二分	对浮点数进行二分逼近	二分法应用
STL 函数	lower_bound / upper_bound 用法	STL 与二分

③核心口诀

第 1 步区间 [0,9]，取中点 mid=4 第 2 步a[4]=16 < 23 → lo=5，砍掉左半 第 3 步区间 [5,9]，mid=7 第 4 步a[7]=56 > 23 → hi=6，砍掉右半 第 5 步区间 [5,6]，mid=5 → a[5]=23 找到！

示例：在有序数组 [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] 中查找 23 —— 每次比较都把区间砍掉一半，10 个元素最多 4 次就锁定（⌈log₂10⌉=4）

🔑 二分法核心

有序才能用二分，单调是前提条件；
每次取中间值，砍掉一半搜索空间；
log n 次搞定，比线性快百万倍！

🔑 二分答案口诀

答案有单调性？二分答案！
猜一个值 mid → 用 check(mid) 验证
满足 → 往更优方向缩；不满足 → 往安全方向缩

🔑 边界防死循环

mid = L + (R - L) / 2 防溢出
收缩方向要明确，L 和 R 必须能动
while(L < R) 配 mid 取舍，保证收敛！

模块 02

知识探究

深入掌握二分查找的实现、二分答案的思想以及实数二分的技巧。

1二分查找基础核心

二分查找的前提条件：数组已排序（升序或降序）。

📏

确定范围

L=左边界, R=右边界

🎯

取中间值

mid = (L+R) / 2

⚖️

比较判断

a[mid] 与目标值比较

✂️

缩小范围

排除一半，继续搜索

📊 可视化：在 [2,5,8,12,16,23,38,56,72,91] 中查找 23

第1轮：L=0, R=9, mid=4, a[4]=16 < 23 → 目标在右半部分

312

416

523

638

756

872

991

a[4]=16 < 23 → 排除左半部分（含mid），L = mid+1 = 5

第2轮：L=5, R=9, mid=7, a[7]=56 > 23 → 目标在左半部分

312

416

523

638

756

872

991

a[7]=56 > 23 → 排除右半部分（含mid），R = mid-1 = 6

第3轮：L=5, R=6, mid=5, a[5]=23 == 23 → 找到！✅

312

416

523

638

756

872

991

a[5]=23 == 目标 → 找到！下标 = 5。仅用 3 轮，而线性查找需要 6 次。

2二分查找三大模板必会

二分查找看似简单，但边界处理非常容易出错。以下三个模板覆盖所有场景：

模板① 标准二分

查找精确等于目标的位置
找到则返回下标
找不到返回 -1
while(L <= R)

模板② 下界查找

找第一个 ≥ target 的位置
即 lower_bound
while(L < R)
mid = L+(R-L)/2

模板③ 上界查找

找第一个 > target 的位置
即 upper_bound
while(L < R)
mid = L+(R-L+1)/2

模板① 标准二分查找

C++精确查找

int bs_find(int a[], int n, int target) {
    int L = 0, R = n - 1;
    while (L <= R) {
        int mid = L + (R - L) / 2;
        if (a[mid] == target) return mid;
        else if (a[mid] < target) L = mid + 1;
        else R = mid - 1;
    }
    return -1; // 没找到
}

模板② 下界查找 (lower_bound)

C++第一个 ≥ target

int bs_lower(int a[], int n, int target) {
    int L = 0, R = n;
    while (L < R) {
        int mid = L + (R - L) / 2;
        if (a[mid] >= target) R = mid;
        else L = mid + 1;
    }
    return L; // 第一个≥target的位置
}

模板③ 上界查找 (upper_bound)

C++第一个 > target

int bs_upper(int a[], int n, int target) {
    int L = 0, R = n;
    while (L < R) {
        int mid = L + (R - L) / 2;
        if (a[mid] > target) R = mid;
        else L = mid + 1;
    }
    return L; // 第一个>target的位置
}

📋 三者对比

模板	循环条件	返回值含义
标准	L <= R	目标下标或 -1
下界	L < R	第一个 ≥ target
上界	L < R	第一个 > target

案例案例1：有序数组查找基础

给定一个升序数组 a = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]，查找目标值 11 的位置。

🔍 详细执行过程

初始：L=0, R=9

第1轮：mid = (0+9)/2 = 4, a[4] = 9 < 11 → L = mid+1 = 5

第2轮：mid = (5+9)/2 = 7, a[7] = 15 > 11 → R = mid-1 = 6

第3轮：mid = (5+6)/2 = 5, a[5] = 11 == 11 → 找到！返回 5 ✅

仅用 3 轮，而线性查找需要 6 次（从下标0扫到下标5）。

C++binary_search.cpp

#include <iostream>
using namespace std;

int main() {
    int a[] = {1,3,5,7,9,11,13,15,17,19};
    int n = 10, target = 11;
    int L = 0, R = n - 1;

while (L <= R) {
        int mid = L + (R - L) / 2;
        if (a[mid] == target) {
            cout << "找到！下标 = " << mid << endl;
            return 0;
        } else if (a[mid] < target) {
            L = mid + 1;  // 目标在右半部分
        } else {
            R = mid - 1;  // 目标在左半部分
        }
    }
    cout << "未找到" << endl;
    return 0;
}

运行结果

找到！下标 = 5

案例案例2：二分答案 — 木材切割高频

有 n 根木材，长度分别为 L₁, L₂, ..., Lₙ。需要切出 k 根等长的小段。问小段的最大长度是多少？

💡 为什么能二分？因为答案具有"单调性"！

如果长度为 x 能切出 k 段 → 比 x 短的也一定能（切更多段）

如果长度为 x 不能切出 k 段 → 比 x 长的也一定不能（切更少段）

所以存在一个分界点：≤ 分界点都满足，> 分界点都不满足。我们要找这个分界点的最大值！

示例：4根木材 [100, 200, 300, 400]，需要切 10 根等长小段。

check(mid)函数：对于长度 mid，每根木材能切 L[i]/mid 段，总和是否 ≥ k？

🔍 二分过程

L=1, R=400（最大可能的长度就是最长木材）

mid=200: check → 100/200+200/200+300/200+400/200 = 0+1+1+2 = 4 < 10 ❌ → R=199

mid=100: check → 1+2+3+4 = 10 ≥ 10 ✅ → 记录答案，L=101（尝试更大）

mid=150: check → 0+1+2+2 = 5 < 10 ❌ → R=149

mid=125: check → 0+1+2+3 = 6 < 10 ❌ → R=124

mid=112: check → 0+1+2+3 = 6 < 10 ❌ → R=111

mid=106: check → 0+1+2+3 = 6 < 10 ❌ → R=105

mid=103: check → 0+1+2+3 = 6 < 10 ❌ → R=102

mid=101: check → 0+1+2+3 = 6 < 10 ❌ → R=100

L=101 > R=100 → 循环结束

答案：100

C++wood_cutting.cpp — 二分答案

#include <iostream>
using namespace std;

int n, k;
int L[10005];

// check函数：长度为mid时，能否切出至少k段？
bool check(int mid) {
    if (mid == 0) return false;
    int cnt = 0;
    for (int i = 0; i < n; i++)
        cnt += L[i] / mid;  // 每根木材能切几段
    return cnt >= k;
}

int main() {
    cin >> n >> k;
    int maxL = 0;
    for (int i = 0; i < n; i++) {
        cin >> L[i];
        maxL = max(maxL, L[i]);
    }

int left = 1, right = maxL, ans = 0;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (check(mid)) {
            ans = mid;        // 记录可行答案
            left = mid + 1;  // 尝试更大
        } else {
            right = mid - 1; // 缩小
        }
    }
    cout << ans << endl;
    return 0;
}

运行结果

输入：4 10
100 200 300 400
输出：100

🔑 二分答案通用框架

① 确定答案范围 [left, right]
② 编写 check(mid) 函数：mid 是否可行？
③ 根据单调性决定收缩方向：可行 → 往更优方向走，不可行 → 往安全方向走
④ 循环直到 left > right，输出记录的 ans

案例案例3：实数二分 — 求平方根经典

不使用 sqrt 函数，用二分法求 √n 的值，精确到小数点后6位。

🔍 详细分析

搜索范围：[0, n]（当 n≥1 时）或 [0, 1]（当 n<1 时）

判断条件：mid² 与 n 的关系

• mid² < n → mid 太小，答案在右半部分 → L = mid

• mid² > n → mid 太大，答案在左半部分 → R = mid

• mid² ≈ n（精度足够）→ 找到答案

终止条件：R - L < 10⁻⁷（比要求的精度多一位）

C++sqrt_binary.cpp — 实数二分

#include <iostream>
#include <iomanip>
using namespace std;

int main() {
    double n;
    cin >> n;

double L = 0, R = max(n, 1.0);

// 二分 100 次，精度远超 10⁻⁶
    for (int i = 0; i < 100; i++) {
        double mid = (L + R) / 2;
        if (mid * mid < n)
            L = mid;
        else
            R = mid;
    }

cout << fixed << setprecision(6) << L << endl;
    return 0;
}

运行结果

输入：2
输出：1.414214

💡 实数二分的两种终止方式

方式一：固定迭代次数（推荐）— 迭代 100 次，每次范围减半，精度达 2⁻¹⁰⁰ ≈ 10⁻³⁰

方式二：判断区间宽度 — while(R - L > 1e-7)，但可能因浮点精度问题死循环

竞赛推荐：固定迭代 100 次，简单安全不会死循环！

案例案例4：STL 二分函数实用

C++ STL 提供了现成的二分查找函数，竞赛中直接使用即可：

函数	功能	返回值	头文件
lower_bound(a, a+n, x)	找第一个 ≥ x 的位置	迭代器（指针）	<algorithm>
upper_bound(a, a+n, x)	找第一个 > x 的位置	迭代器（指针）	<algorithm>
binary_search(a, a+n, x)	判断 x 是否存在	bool（true/false）	<algorithm>

C++stl_binary.cpp

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int a[] = {1, 3, 3, 5, 7, 7, 7, 9};
    int n = 8;

// lower_bound: 第一个 ≥ 3 的位置
    int pos1 = lower_bound(a, a + n, 3) - a;
    cout << "lower_bound(3) = " << pos1 << endl;  // 1

// upper_bound: 第一个 > 3 的位置
    int pos2 = upper_bound(a, a + n, 3) - a;
    cout << "upper_bound(3) = " << pos2 << endl;  // 3

// 元素 3 出现的次数
    cout << "3 出现了 " << pos2 - pos1 << " 次" << endl;  // 2

// binary_search: 判断是否存在
    cout << "7 存在: " << binary_search(a, a+n, 7) << endl;  // 1
    cout << "4 存在: " << binary_search(a, a+n, 4) << endl;  // 0

return 0;
}

运行结果

lower_bound(3) = 1
upper_bound(3) = 3
3 出现了 2 次
7 存在: 1
4 存在: 0

🔑 STL 二分使用技巧

统计元素 x 出现次数：upper_bound(x) - lower_bound(x)
找 x 的第一次出现：lower_bound(x)
找 x 的最后一次出现：upper_bound(x) - 1
找比 x 大的最小元素：*upper_bound(x)
注意：数组必须已排序！

模块 03

实践应用

通过详细分析的题目，巩固二分查找和二分答案的实战能力。

题1查找元素（基础二分）

题目：在有序数组 [2, 4, 6, 8, 10, 12, 14, 16, 18, 20] 中查找 14。手动模拟二分过程，写出每轮的 L、R、mid 和比较结果。

查看参考答案

详细模拟过程：

轮次	L	R	mid	a[mid]	比较	操作
1	0	9	4	10	10 < 14	L = 5
2	5	9	7	16	16 > 14	R = 6
3	5	6	5	12	12 < 14	L = 6
4	6	6	6	14	14 == 14	找到！返回 6

共 4 轮找到目标。如果用线性查找，需要 7 次比较（从 a[0] 到 a[6]）。

💡 解析思路：二分三要素：① 单调（有序）才可二分；② 区间定义保持不变（闭区间 [lo,hi] 就用 lo=mid+1 / hi=mid-1）；③ 终止条件 lo>hi 时返回 -1。

⚠️ 易错：mid=(lo+hi)/2 在 lo、hi 都接近 INT_MAX 时会溢出，安全写法是 mid=lo+(hi-lo)/2；另外循环条件是 while(lo<=hi)（闭区间），漏掉等号会漏查边界元素。

题2木材切割（二分答案）

题目：有 5 根木材，长度分别为 [200, 350, 400, 500, 600]。需要切出 15 根等长的小段。小段的最大长度是多少？

提示：这是典型的二分答案问题。答案范围 [1, 600]，check(mid) = 各木材切出的段数之和 ≥ 15？

查看参考答案

分析：答案具有单调性 — 长度越短，能切出的段数越多。

check 函数：cnt = Σ (L[i] / mid)，判断 cnt ≥ 15

关键二分步骤：

mid	200/mid	350/mid	400/mid	500/mid	600/mid	总段数	结果
300	0	1	1	1	2	5	❌ <15
150	1	2	2	3	4	12	❌ <15
75	2	4	5	6	8	25	✅ ≥15
112	1	3	3	4	5	16	✅ ≥15
131	1	2	3	3	4	13	❌ <15
121	1	2	3	4	4	14	❌ <15
116	1	3	3	4	5	16	✅ ≥15

继续二分下去...最终答案 = 120

验证：200/120 + 350/120 + 400/120 + 500/120 + 600/120 = 1+2+3+4+5 = 15 ≥ 15 ✅

而 mid=121: 1+2+3+4+4 = 14 < 15 ❌，故最大长度为 120

最终精确答案 = 120（mid=121 时只能切 14 块 < 15）

💡 解析思路：「答案具有单调性」就能二分答案：长度 L 越长 → 段数越少。求「满足段数≥k 的最大 L」，就是在「可行区间」上找右边界：mid 可行 → 记录并尝试更大的 L=mid+1；不可行 → hi=mid-1。

⚠️ 易错：① 段数用整除累加时会溢出 int，要开 long long；② 二分答案的 check() 里数组只需要遍历一次 O(n)，总复杂度 O(n log(maxL))，别写成双重循环。

题3进击的奶牛（NOIP真题改编）

题目：有 n 个牛棚在一条直线上，位置分别为 x₁, x₂, ..., xₙ。要放入 c 头奶牛，使得任意两头牛之间的最小距离尽可能大。求这个最大化的最小距离。

提示："最大化最小值"是二分答案的经典模式！check(mid) = 能否放置 c 头牛且相邻距离 ≥ mid？

查看参考答案

核心思路：二分"最小距离"，用贪心验证。

答案范围：[1, xₙ - x₁]（最大距离不超过最远两牛棚之差）

check(mid)：贪心放置 — 第一头牛放在 x₁，之后每头牛放在"距上一头 ≥ mid 的第一个位置"。如果能放 ≥ c 头就返回 true。

示例：牛棚 [1, 2, 4, 8, 9]，放 3 头牛

mid=3: 第1头@1, 第2头@4(≥1+3), 第3头@8(≥4+3) → 3头 ✅

mid=4: 第1头@1, 第2头@8(≥1+4=5,最近的), 第3头@(≥8+4=12,无) → 2头 ❌

答案 = 3

#include <iostream>
#include <algorithm>
using namespace std;
int n, c, x[100005];
bool check(int d) {
    int cnt = 1, last = x[0];
    for(int i = 1; i < n; i++)
        if(x[i] - last >= d) {
            cnt++; last = x[i];
        }
    return cnt >= c;
}
int main() {
    cin >> n >> c;
    for(int i=0;i<n;i++) cin >> x[i];
    sort(x, x + n);
    int L=1, R=x[n-1]-x[0], ans=0;
    while(L<=R){
        int mid=L+(R-L)/2;
        if(check(mid)){ans=mid;L=mid+1;}
        else R=mid-1;
    }
    cout << ans << endl;
}

💡 解析思路：「最大化最小间距」是经典二分答案模型：间距 d 越大 → 能放的牛越少，具有单调性。check(d) 用贪心验证：从最左端开始，只要与前一头牛距离 ≥d 就放。

⚠️ 易错：牛棚坐标要先排序（题目可能乱序给）；check 贪心时第一头牛必须放在第一个牛棚（放在更靠后只会更差）。

知识板块	必须记住的核心
前提条件	搜索空间必须具有单调性
时间复杂度	O(log n)，每步缩小一半
标准二分	while(L <= R)，找到精确值
下界查找	while(L < R)，找第一个 ≥ target
上界查找	while(L < R)，找第一个 > target
二分答案	答案有单调性 → 二分值 + check() 验证
实数二分	固定迭代100次，精度足够
STL 函数	lower_bound / upper_bound / binary_search
防溢出	mid = L + (R - L) / 2 而非 (L+R)/2

✅ 正确

用固定迭代次数：for(int i=0; i<100; i++)。100次二分精度达 2⁻¹⁰⁰，远超需求。

口诀：实数二分迭代100次，简单安全不死循环！

速查二分法速查表

场景	方法	时间复杂度
有序数组查目标	标准二分 while(L<=R)	O(log n)
找第一个≥target	lower_bound / 模板②	O(log n)
找第一个>target	upper_bound / 模板③	O(log n)
最大化最小值	二分答案 + check	O(n log V)
最小化最大值	二分答案 + check	O(n log V)
求实数解	实数二分（迭代100次）	O(100)
单峰函数极值	三分法	O(log n)

📌知识点笔记卡

🔍 二分核心

有序+单调

每次砍半

O(log n)

📐 三大模板

标准：找精确值

下界：第一个≥

上界：第一个>

🎯 二分答案

答案有单调性

猜mid+check验证

最大化最小/最小化最大

🔢 实数二分

迭代100次

精度远超需求

不会死循环

⚠️ 防坑指南

mid用减法防溢出

收缩方向要正确

先排序再二分

📚 STL函数

lower_bound

upper_bound

binary_search

课后练习

分层练习作业

考点：每次把候选区间折半，求“折半多少次才能锁定唯一答案”，即 2 的多少次方超过 10⁶。

易错：算得 log₂10⁶≈19.93 后直接取 19，忘记次数必须是整数、需要向上取整。

A4编程题

给定一个升序数组和多个查询，对每个查询用二分法找出目标值的位置（不存在输出-1）。

查看参考答案

#include <iostream>
using namespace std;
int a[100005];
int main() {
    int n, q;
    cin >> n >> q;
    for(int i=0;i<n;i++) cin >> a[i];
    while(q--) {
        int target; cin >> target;
        int L=0, R=n-1, ans=-1;
        while(L<=R) {
            int mid=L+(R-L)/2;
            if(a[mid]==target){ans=mid;break;}
            else if(a[mid]<target) L=mid+1;
            else R=mid-1;
        }
        cout << ans << endl;
    }
}

思路：对每次查询维护 L、R 两个边界，用 mid=L+(R−L)/2 求中点，比较后收缩区间，直到 L>R 为止。

易错：边界更新写成 L=mid 或 R=mid，区间不再缩小会陷入死循环；中点写成 (L+R)/2 在极端数据下还可能溢出。

🟡 B组 · 提高（4题）

B1编程题

在有序数组中找第一个 ≥ target 的位置（lower_bound），如果所有元素都小于 target，返回 n。

查看参考答案

#include <iostream>
using namespace std;
int a[100005];
int main() {
    int n, target;
    cin >> n >> target;
    for(int i=0;i<n;i++) cin >> a[i];
    int L=0, R=n; // 注意 R=n 不是 n-1
    while(L < R) {
        int mid = L + (R - L) / 2;
        if(a[mid] >= target) R = mid;
        else L = mid + 1;
    }
    cout << L << endl; // L 就是答案
}

关键：R 初始化为 n（而非 n-1），因为答案可能是 n（所有元素都小于 target）。

思路：把右边界设为 n（哨兵位置），用 L

B2编程题

实数二分：不用 sqrt 函数，求 √n 精确到小数点后8位（n≤10⁹）。

查看参考答案

#include <iostream>
#include <iomanip>
using namespace std;
int main() {
    double n; cin >> n;
    double L = 0, R = max(n, 1.0);
    for(int i=0;i<100;i++){ // 迭代100次
        double mid = (L+R)/2;
        if(mid*mid < n) L = mid;
        else R = mid;
    }
    cout << fixed << setprecision(8) << L << endl;
}

说明：100次迭代精度达 2⁻¹⁰⁰ ≈ 10⁻³⁰，远超 10⁻⁸ 的需求。

思路：实数二分不需要精确的中点判定，直接固定迭代 100 次即可达到 10⁻⁸ 级别的精度。

易错：把 while(R-L>eps) 的 eps 设得比 double 精度还小，循环永不结束；或右边界忘记取 max(n,1.0)，n<1 时答案落在区间之外。

B3编程题

给定有序数组和 target，统计 target 在数组中出现的次数。要求 O(log n)。

查看参考答案

#include <iostream>
#include <algorithm>
using namespace std;
int a[100005];
int main() {
    int n, target;
    cin >> n >> target;
    for(int i=0;i<n;i++) cin >> a[i];
    int cnt = upper_bound(a, a+n, target) 
            - lower_bound(a, a+n, target);
    cout << cnt << endl;
}

核心：upper_bound - lower_bound = 元素出现次数。两次二分，总复杂度 O(log n)。

思路：用 lower_bound 和 upper_bound 分别求出第一次出现的位置和最后一次出现的后一位，两者相减即出现次数。

易错：把次数写成 upper_bound−lower_bound+1（多算一个）；或没有处理 target 不存在时结果为 0 的情况。

B4编程题

给定一个单调递增函数 f(x) = x³ + 2x，求 f(x) = target 的 x 值（精确到10⁻⁶）。

查看参考答案

#include <iostream>
#include <iomanip>
using namespace std;
double f(double x) { return x*x*x + 2*x; }
int main() {
    double target; cin >> target;
    double L = -1000, R = 1000;
    for(int i=0;i<100;i++){
        double mid = (L+R)/2;
        if(f(mid) < target) L = mid;
        else R = mid;
    }
    cout << fixed << setprecision(6) << L << endl;
}

思路：f(x) 单调递增 → 可用实数二分。初始范围取 [-1000, 1000] 足够覆盖大部分情况。

易错：把判断条件 f(mid)

🔴 C组 · 挑战（4题）

C1初赛真题

在 n 个元素的有序数组中进行二分查找，最坏情况下的比较次数为（）

A. n B. n/2 C. ⌊log₂n⌋+1 D. n²

查看参考答案

答案：C. ⌊log₂n⌋+1

二分查找最坏情况下需要 ⌊log₂n⌋+1 次比较。例如 n=10 时，⌊log₂10⌋+1 = 3+1 = 4 次。

考点：二分查找最坏情况下的比较次数公式为 ⌊log₂n⌋+1，可以代入小规模的 n 验证。

易错：把公式记成 ⌈log₂n⌉ 或 log₂n，代 n=10 就算不出正确答案 4。

C2二分答案

有 n 本书要分给 m 个学生，每本书有不同的页数。每个学生分到连续的一段书。要求使"分到最多页的学生"的页数尽量少。求这个最小值。

查看参考答案

分析："最小化最大值" → 典型二分答案！

答案范围：[max(pages), sum(pages)]

check(mid)：贪心地分配，每段不超过 mid 页，看需要分几段。如果段数 ≤ m 则可行。

#include <iostream>
using namespace std;
int n, m, p[505];
bool check(int limit) {
    int cnt = 1, sum = 0;
    for(int i=0;i<n;i++){
        if(p[i]>limit) return false;
        if(sum+p[i]>limit){cnt++;sum=p[i];}
        else sum+=p[i];
    }
    return cnt<=m;
}
int main() {
    cin >> n >> m;
    int mx=0, sm=0;
    for(int i=0;i<n;i++){cin>>p[i];mx=max(mx,p[i]);sm+=p[i];}
    int L=mx, R=sm, ans=sm;
    while(L<=R){
        int mid=L+(R-L)/2;
        if(check(mid)){ans=mid;R=mid-1;}
        else L=mid+1;
    }
    cout << ans << endl;
}

易错：check 里漏掉“某本书页数本身超过 limit 就不可行”的判断；或二分下界取 0 而不是 max(pages)。

C3综合分析

给定一个旋转排序数组（如 [4,5,6,7,0,1,2]），在其中查找目标值。要求 O(log n)。

查看参考答案

分析：旋转数组分两段有序。每次二分后，判断 mid 在哪一段，再决定目标在哪边。

#include <iostream>
using namespace std;
int a[10005];
int main() {
    int n, target;
    cin >> n >> target;
    for(int i=0;i<n;i++) cin >> a[i];
    int L=0, R=n-1;
    while(L<=R){
        int mid=L+(R-L)/2;
        if(a[mid]==target){cout<<mid; return 0;}
        if(a[L]<=a[mid]){ // 左半有序
            if(a[L]<=target&&target<a[mid]) R=mid-1;
            else L=mid+1;
        } else { // 右半有序
            if(a[mid]<target&&target<=a[R]) L=mid+1;
            else R=mid-1;
        }
    }
    cout << -1;
}

核心：每次判断 mid 在左段还是右段（a[L]≤a[mid] → 左段有序），然后在有序的那半段中判断目标位置。

易错：判断 mid 落在左段还是右段的单调性条件写错（如漏掉 a[L]≤a[mid] 这一层分支），会把目标区间选反，最终误输出 -1。

C4综合编程

用二分法求方程 x⁵ + x³ + x = 100 的实数根，精确到 10⁻⁸。

查看参考答案

#include <iostream>
#include <iomanip>
using namespace std;
double f(double x){return x*x*x*x*x+x*x*x+x;}
int main(){
    double L=0, R=10;
    for(int i=0;i<100;i++){
        double mid=(L+R)/2;
        if(f(mid)< 100) L=mid;
        else R=mid;
    }
    cout<<fixed<<setprecision(8)<<L<<endl;
    // 输出约 2.42214183
}

分析：f(x) = x⁵+x³+x 在 [0,10] 上单调递增（各项均递增），f(0)=0 < 100, f(10)>100，所以有唯一解。实数二分即可。

易错：把 if(f(mid)<100) 对应的收缩方向写反（应让 L=mid），结果会收敛到区间的错误端点。

🏆 洛谷原题精选（20题）

以下题目均来自洛谷（luogu.com.cn），涵盖二分查找、二分答案、实数二分等核心考点。建议按顺序从易到难刷。

P2249

#1 基础：查找

入门

在有序数组中查找给定值的位置，基础二分练习。

P1024

#2 一元三次方程求解

入门

用实数二分求三次方程的实数根。

P1102

#3 A-B 数对

入门

排序+二分/双指针，找差值为C的数对个数。

P1824

#4 进击的奶牛

普及

经典"最大化最小值"，二分答案+贪心验证。

P3853

#5 路标设置

普及

"最小化最大值"，二分相邻路标最大距离。

P3743

#6 kotori的设备

普及

实数二分答案，判断设备能否在时间内充满。

P1873

#7 [COCI 2011] EKO/砍树

普及

二分锯片高度，使砍下的木材总量恰好达标。

P1419

#8 寻找段落

普及

二分答案+前缀和+单调队列/滑动窗口验证。

P2440

#9 木材加工

入门

经典二分答案入门题，切出K段等长木材。

P1525

#10 [NOIP2010]关押罪犯

普及+

二分答案+并查集/二分图判定。

P1661

#11 扩散

普及

二分时间，判断所有点是否已被覆盖。

P1083

#12 [NOIP2012]借教室

普及+

二分答案+差分数组验证，NOIP经典真题。

P2678

#13 [NOIP2015]跳石头

普及

"最大化最小距离"，二分答案经典题。

P1182

#14 数列分段 Section II

入门

最小化最大值，二分答案入门必刷。

P1577

#15 切绳子

入门

实数二分答案，切出K根等长绳子。

P2884

#16 [USACO] Monthly Expense

普及

"最小化最大月开销"，二分答案+贪心。

P3978

#17 [TJOI2015] 概率论

提高

二分+概率计算，需要数学推导。

P9050

#18 [CSP-S2023] 一元二次方程

普及+

实数二分求精确根，注意精度处理。

P7968

#19 [CSP-J2021] 网络连接

普及

二分查找+字符串匹配综合题。

P1678

#20 烦恼的高考志愿

入门

二分查找+lower_bound实战应用。

💡 刷题建议

入门阶段（#1, #9, #14, #15, #20）：先掌握基础二分查找和简单二分答案

提高阶段（#4, #7, #13, #11, #12）：刷经典二分答案真题

冲刺阶段（#8, #10, #18, #17）：挑战综合性强的难题

每道题都要自己想至少30分钟再看题解！

情景导航

翻字典

排查电路故障

调音量

量体温

知识探究

确定范围

取中间值

比较判断

缩小范围

📊 可视化：在 [2,5,8,12,16,23,38,56,72,91] 中查找 23

模板① 标准二分

模板② 下界查找

模板③ 上界查找

模板① 标准二分查找

模板② 下界查找 (lower_bound)

模板③ 上界查找 (upper_bound)

📋 三者对比

💡 实数二分的两种终止方式

实践应用

总结提升

💡 二分法只能处理"单调"，三分法能处理"单峰"！

💡 学完本讲，你应该掌握的7项能力

学习检测

mid = (L + R) / 2 整数溢出

while(L < R) 死循环

未排序就用二分

二分答案的 check 写错方向

实数二分用 while 判断精度

🔍 二分核心

📐 三大模板

🎯 二分答案

🔢 实数二分

⚠️ 防坑指南

📚 STL函数

分层练习作业

🟢 A组 · 基础（4题）

二分查找的时间复杂度是（）

二分查找的前提条件是（）

在1~1000000中猜一个数，用二分策略最多需要猜（）次

给定一个升序数组和多个查询，对每个查询用二分法找出目标值的位置（不存在输出-1）。

🟡 B组 · 提高（4题）

在有序数组中找第一个 ≥ target 的位置（lower_bound），如果所有元素都小于 target，返回 n。

实数二分：不用 sqrt 函数，求 √n 精确到小数点后8位（n≤10⁹）。

给定有序数组和 target，统计 target 在数组中出现的次数。要求 O(log n)。

给定一个单调递增函数 f(x) = x³ + 2x，求 f(x) = target 的 x 值（精确到10⁻⁶）。

🔴 C组 · 挑战（4题）

在 n 个元素的有序数组中进行二分查找，最坏情况下的比较次数为（）

有 n 本书要分给 m 个学生，每本书有不同的页数。每个学生分到连续的一段书。要求使"分到最多页的学生"的页数尽量少。求这个最小值。

给定一个旋转排序数组（如 [4,5,6,7,0,1,2]），在其中查找目标值。要求 O(log n)。

用二分法求方程 x⁵ + x³ + x = 100 的实数根，精确到 10⁻⁸。

🏆 洛谷原题精选（20题）

💡 刷题建议