专题7 · 二分（一）
二分不止是「在有序数组里找数」——
它是一种每次砍掉一半搜索范围的通用思想，能用在整数、浮点数甚至答案上。
本讲先把二分的两套模板与两个高频坑彻底讲透。
有序 + 一刀两断 = 每次砍一半
🔍 顺序查找
从头到尾一个个比，最坏要走 n 步，复杂度 O(n)。
1 亿个元素、查一次就要 1 亿次比较。
⚡ 二分查找
每次拿中间值比一下，根据大小直接排除一半，复杂度 O(log n)。
1 亿个元素只需约 27 次比较——这就是量级差距。
🖼️ 看图：为什么二分快这么多（16 个格子里找一个数）
① 序列/函数必须单调（有序）；
② 每次比较后，能明确判断答案在左半边还是右半边。
很多「二分写不出来」的题，其实是单调性没找对，不是模板不会。
左闭右闭 vs 左闭右开：别混着写
📘 模型 A：左闭右闭 [l, r]
while(l <= r){ mid = (l+r)/2; if(a[mid] >= q) r = mid-1; else l = mid+1; }
区间包含 r，所以收缩时要跨过 mid（mid-1 / mid+1）。
📗 模型 B：左闭右开 [l, r)
while(l < r){ mid = (l+r)/2; if(a[mid] >= q) r = mid; else l = mid+1; }
区间不含 r，所以左半边收缩时 r = mid（不减 1）。
while(l<r) 里却写 r=mid-1，或者 while(l<=r) 里写 r=mid。结果是死循环或漏解。选一套，从头到尾只用那一套。找左边界 / 找右边界
① 找最小满足值（左边界）
while(l < r){ mid = (l+r)/2; // 下取整 if(check(mid)) r = mid; else l = mid+1; } return l;
条件成立时，答案可能是 mid 也可能在左边，所以 r=mid。
② 找最大满足值（右边界）
while(l < r){ mid = (l+r+1)/2; // ★ 上取整 if(check(mid)) l = mid; else r = mid-1; } return l;
条件成立时，答案可能是 mid 也可能在右边，所以 l=mid。
l+1==r 时，若 mid 取下取整会等于 l，此时 l=mid 毫无变化 → 死循环。上取整让 mid 取到 r，才能推进。这是二分第一大坑。check 成立时是 l = mid 还是 r = mid：只要是 l = mid，mid 就必须上取整（+1）。写成配套的一对，永远不会死循环。整数二分 · 指针移动模拟器
数的范围：两次二分找左右边界
升序序列中，对每个询问 q，输出 q 第一次和最后一次出现的位置；不存在输出 −1 −1。
🔍 左边界
找第一个 ≥ q 的位置。
用模板①（找最小满足值）。
关键：找到后必须验证该位置的值是否真的等于 q，否则是 -1。
🔍 右边界
找最后一个 ≤ q 的位置。
用模板②（找最大满足值）。
同样要验证值等于 q。
a[ans]==q。漏掉这步，不存在的数会返回一个错误的下标。数的范围 · 代码走读
int lowerPos(int n, int q){ // 第一个 >= q 的位置 int l=1, r=n, ans=-1; while(l <= r){ int mid = (l+r)/2; if(a[mid] >= q){ ans=mid; r=mid-1; } else { l=mid+1; } } return (ans!=-1 && a[ans]==q) ? ans : -1; // ★ 验证 } int upperPos(int n, int q){ // 最后一个 <= q 的位置 int l=1, r=n, ans=-1; while(l <= r){ int mid = (l+r)/2; if(a[mid] <= q){ ans=mid; l=mid+1; } else { r=mid-1; } } return (ans!=-1 && a[ans]==q) ? ans : -1; // ★ 验证 }
mid=(l+r)/2 在 l、r 接近 2×10⁹ 时可能溢出，保险写法 l+(r-l)/2；② 数组要开到 10⁶+5 且放全局；③ 必须 ios::sync_with_stdio(false)，10⁵ 次查询不用快读会超时。浮点二分：把「砍一半」用在实数上
🆚 与整数二分的差别
- 没有「相邻」概念，不能用 l+1==r 结束。
- 循环条件改为精度控制：
while(r-l > 1e-8)。 - 收缩时直接 r=mid / l=mid，不需要 ±1。
- 不会出现死循环，也不存在模板选择问题。
🧠 精度怎么定
题目要求保留 6 位小数，循环精度取 1e-8（比要求再小两位），留足安全余量。
或者干脆固定跑 100 次：区间每次减半，100 次后精度远超 1e-8，简单又好记。
数的三次方根 · 代码走读
double l = -100, r = 100, mid; // 100^3 已远大于数据上限 while(r - l > 1e-8){ // ★ 精度控制，不是 l<=r mid = (l + r) / 2; if(mid*mid*mid >= n) r = mid; // x^3 单调递增 else l = mid; } cout << fixed << setprecision(6) << l << "\n";
✅ 关键点
f(x)=x³ 在整个实数域单调递增，所以能二分。
区间必须覆盖答案：n 最大 10⁴，³√10⁴ ≈ 21.5，取 ±100 足够。
⚠️ 输出格式
必须 fixed << setprecision(6)，否则默认有效数字输出，格式不对就是 WA。
头文件别忘 <iomanip>。
浮点二分 · 区间收敛模拟器
二分高频易错辨析
① 模板②（找最大满足值）里 mid 为什么写成 (l+r+1)/2？
② 二分跑完得到位置 ans，接下来必须做什么？
③ 浮点二分的循环条件应该写成？
一道题 100 分是分档给的——不会正解也要先拿保底
复赛一道题的 100 分由十几到二十几个测试点组成， 前面几档专门为「没想出正解的人」准备。四道题各拿 30~40 分， 加起来往往就是一等奖和二等奖的分界。
① 特判档：先别想算法，看数据范围表
题目给的数据范围表就是出题人给你的送分清单。看到「n = 1」「只有一组数据」这类一行，
就先写个 if 直接输出答案。2 分钟换 5~10 分，全场最划算。
② 暴力档：按题意最直白地写一遍
多重循环、DFS 全枚举、朴素 O(n³)……不要优化，只要保证最小那档全对。 它既是保底分，又是后面对拍的标尺——没有它你无法证明正解是对的。
③ 特殊性质档：题目里那句「若……」
常见的送分性质：数据已经有序、所有值完全相同、规模小到可以 O(n²)、 只出现一种类型。题目写出来就是让你拿的，专门写一份即可。
④ 正解档：思路定了，就赢了八成
考场上的时间几乎都花在想思路上，不是写代码。写完先跑样例， 再用第 ② 档的暴力版造小数据对拍——这是唯一能证明你思路对的办法。
本讲 2 道题，各自的四档怎么走
数的范围 · RANGE
第1档 · 2 分钟
数组长度 1 → 判等后输出 0 0 或 -1 -1
第2档 · 8 分钟
从左往右扫找第一个、从右往左扫找最后一个，n ≤ 10⁵ 稳过
第3档 · 10 分钟
只做第一问（找第一次出现），先拿一半分
第4档 · 15 分钟
两套模板：找左端点 a[mid]>=x → r=mid；找右端点 a[mid]<=x → l=mid
数的三次方根 · CUBERT
第1档 · 2 分钟n == 0 → 0.000000；n 是完全立方数先手算一遍
第2档 · 8 分钟
以 1e-4 为步长暴力扫一遍定位区间，再逐步细化到 1e-6
第3档 · 10 分钟n ≤ 1 → 答案就是 n 本身
第4档 · 15 分钟
浮点二分 while (r−l > 1e-7)，比较 mid³ < n，输出 %.6f
0–5 分钟 读题 + 圈出数据范围表里最小的那几档 → 5–15 分钟 写完第 1、2 档并先交一次（保住 20~30 分）→ 15–40 分钟 冲第 3、4 档 → 40–50 分钟 造小数据对拍、检查
freopen 与文件名。本讲知识树与自检清单
🌳 知识树
前提：单调 + 可判定左右。
整数：两套模板 —— 找左边界（r=mid，下取整）、找右边界（l=mid，上取整）。
浮点：精度控制 + r=mid / l=mid，无死循环。
STL：lower_bound / upper_bound / binary_search。
✅ 考场 N 步自检
- 单调性找对了吗？说不出单调性就别写二分。
- 模板选的是哪一套？全程别混用。
- 是
l = mid吗？是的话 mid 必须 +1。 - mid 会不会溢出？用
l + (r-l)/2更稳。 - 找到后验证了吗？（整数二分必查）
- 浮点题
fixed << setprecision加了吗？