C++ 算法考级专栏
🎨 视觉封面【GESP/CSP考点精讲】GESP五级 / CSP-J 必背:二分查找为什么会死循环?mid=(l+r)/2 与 (l+r+1)/2 终极判定指南
算法竞赛圈流传着一句经典的自嘲:“二分查找思路只需十秒钟,调试边界死循环却要两小时!”为什么明明只是在一个有序数组里折半找数,有的时候写 mid = (l + r) / 2 顺畅通关,有的时候把 r = mid 换成 l = mid,程序就瞬间卡死在 while (l < r) 里触发 TLE(运行超时)?当数组中存在一连串相等元素(如 1, 3, 5, 5, 5, 7)时,怎样才能精准定位**第一个 5(左边界)与最后一个 5(右边界)**而绝不漏解或越界?在 GESP 五级认证以及 CSP-J/S 初赛与复赛中,二分查找的“单调分界点”本质、左右边界两大无死循环模板的底层数学证明、整数加法防溢出写法,以及 C++ STL lower_bound 与 upper_bound 的精准运用,是贯穿初赛完善程序题与复赛高效算法设计的核心基石。本文将带你从数学根源上终结二分边界混乱。
🎯 考纲锚点与核心痛点
📍 对应考点:深刻理解二分查找的单调性前提与 折半机制,熟练掌握左边界(First True)与右边界(Last True)两套标准整数二分模板、死循环产生的数学充要条件,以及 STL
lower_bound/upper_bound函数原理与边界判定。 🎯 适用等级:GESP 五级考点 | CSP-J/S 初赛/复赛必考
在考场手写二分或做初赛阅读/完善程序题时,考生最常栽在以下三大痛点上:
- “凭感觉乱凑
+1、-1与<=,一遇相邻区间当场死循环”:搞不清while (l < r)与while (l <= r)混用的后果,更不明白为什么分支里一旦出现l = mid,中点公式不加1就会在 时原地踏步永不退出; - “把二分狭隘理解为‘找某个相等的数’,面对重复元素束手无策”:一旦数组含有重复值(如
[2, 5, 5, 5, 8]),朴素找到a[mid] == 5就直接return mid的写法只能随机撞上其中一个5,根本无法求出目标值的首次出现位置或出现总次数; - “忽略‘全域无解’与
(l + r)爆int两大隐蔽杀手”:二分缩界结束得到l == r后忘记检验该位置是否真正满足题目要求,或者在大值域(如 )下直接写(l + r) / 2导致有符号整数相加溢出变负数,瞬间引发数组越界 RE!
🧠 一、 核心原理深度拆解(有理论)
1. 二分的真正本质:不是“大海捞针找值”,而是“卡死 0/1 单调分界线”!
许多初学者之所以觉得二分条件千变万化,是因为把二分当成了“在数组里找等于 x 的元素”。事实上,二分查找的唯一本质,是在一段具有“二段单调性(0/1 单调性)”的区间上,用每次折半排除一半无效空间的手段,精准锁定左半段与右半段的交界点!
哪怕原数组包含大量重复元素,只要我们定义一个布尔判定性质 check(i),就能把整个区间映射为前半段全是一种状态、后半段全是另一种状态的“黑白分界带”:
====================================================================================
【二分本质:把含重复元素的有序数组映射为 0/1 二段单调区间】
原升序数组 a[0..7]: [ 1, 3, 5, 5, 5, 7, 9, 11 ]
数组下标 idx : 0 1 2 3 4 5 6 7
▶ 模型 A(找左边界:第一个 >= 5 的位置,即 5 首次出现下标 2):
性质 check(i): a[i] >= 5 ➔ [ 假, 假, | 真, 真, 真, 真, 真, 真 ]
0 0 | 1 1 1 1 1 1
▲ 锁定右半段第一个 1(下标 2)!
▶ 模型 B(找右边界:最后一个 <= 5 的位置,即 5 末次出现下标 4):
性质 check(i): a[i] <= 5 ➔ [ 真, 真, 真, 真, 真, | 假, 假, 假 ]
1 1 1 1 1 | 0 0 0
▲ 锁定左半段最后一个 1(下标 4)!
====================================================================================每做一次 mid 判定,都能严格砍掉整整一半不可能成为分界点的元素。长度为 的区间最多只需折半 次即可缩减为单点(l == r):哪怕 ,,最多 30 次比较就能从十亿数据中一剑封喉,时间复杂度恒为 ,额外空间复杂度仅为 !
2. 终结死循环:为什么 r = mid 不加 1,而 l = mid 必须加 1?
在竞赛实战中,最稳健、绝不漏解的写法是闭区间收敛法 while (l < r)——始终保持真正的答案被夹在闭区间 [l, r] 内部,循环退出时必然有 l == r,左右指针合二为一指向唯一候选点!
根据分界点落在右半段起点还是左半段终点,所有整数二分严格且唯一地归结为以下两套黄金模板:
| 模板类型 | 目标含义 | 满足条件时的缩界 | 不满足时的缩界 | 唯一配套 mid 公式 |
|---|---|---|---|---|
| 模板一(左边界) | 找第一个满足右半区性质的位置(如首个 >= x) |
r = mid(答案在 mid 或其左边) |
l = mid + 1( mid 必不是,去右边找) |
l + (r - l) / 2(向下取整 ) |
| 模板二(右边界) | 找最后一个满足左半区性质的位置(如末个 <= x) |
l = mid(答案在 mid 或其右边) |
r = mid - 1( mid 必不是,去左边找) |
l + (r - l + 1) / 2(向上取整 ) |
🔬 死循环的底层数学真相:相邻双元素区间 [l, l + 1] 的生死审判!
为什么两套模板的 mid 公式只差一个 + 1,写反了就会死循环?答案就藏在区间缩减到只剩最后两个相邻下标 r = l + 1(例如 l = 3, r = 4)的那一瞬间!
在 C++ 非负整数除法中,/ 默认向下取整:
- 当
l = 3, r = 4时,不加1的公式算出mid = 3 + (4 - 3) / 2 = 3,即mid与左端点l完全重合(mid == l)! - 当
l = 3, r = 4时,加了1的公式算出mid = 3 + (4 - 3 + 1) / 2 = 4,即mid与右端点r完全重合(mid == r)!
我们把这两种取整代入 l = 3, r = 4 检验两条分支是否都能让区间严格变短:
====================================================================================
【生死审判现场:当区间仅剩相邻两个元素 l = 3, r = 4 时】
❌ 致命错误组合:代码里有 l = mid,却配了向下取整 mid = l + (r - l) / 2
➔ 算出 mid = 3 + (4 - 3) / 2 = 3(注意:此时 mid == l == 3!)
├── 若分支走 r = mid - 1 ➔ r = 2(退出循环)
└── 若分支走 l = mid ➔ l = 3!区间从 [3, 4] 变成 [3, 4],纹丝不动!
下一轮还是 l = 3, r = 4 ➔ mid = 3 ➔ l = 3 …… 永久卡死,100% 死循环 TLE!
✅ 黄金正确组合:代码里有 l = mid,严格配向上取整 mid = l + (r - l + 1) / 2
➔ 算出 mid = 3 + (4 - 3 + 1) / 2 = 4(此时 mid == r == 4!)
├── 若分支走 l = mid ➔ l = 4!区间变为 [4, 4],l == r 正常退出!
└── 若分支走 r = mid - 1 ➔ r = 3!区间变为 [3, 3],l == r 正常退出!
两条分支全部严格缩小区间长度,死循环从数学上彻底灰飞烟灭!
====================================================================================同理反推:如果代码里写的是 r = mid 与 l = mid + 1,却误配了加 1 的向上取整,那么在 l = 3, r = 4 时 mid = 4 = r,一旦进入 r = mid 分支,区间同样从 [3, 4] 原地踏步变成 [3, 4] 陷入死循环!
3. 防溢出铁律与 C++ STL 二分双神剑:lower_bound & upper_bound
(1)为什么老手从不写 (l + r) / 2,而坚持写 l + (r - l) / 2?
假设 l 和 r 都是 int 类型(最大值约为 )。当二分范围较大,某一步出现 时,两数本身都没超 int,但先算加法 l + r = 3.3 \times 10^9 会瞬间撑爆 32 位有符号整数上限,溢出回绕成一个巨大的负数!拿负数去访问数组 a[mid] 会当场引发 RE(段错误)。而改写为等价恒等式 l + (r - l) / 2(或加一版 l + (r - l + 1) / 2),差值 r - l 绝不会超过区间长度,彻底根绝加法溢出隐患!
(2)<algorithm> 标准库二分双神剑
对于已经按升序排好的数组 a[0..n-1](或 std::vector<int> v),C++ STL 已经帮我们封装好了底层基于左边界二分的两个 神仙函数:
lower_bound(a, a + n, x):在半开区间[a, a + n)中二分查找**第一个大于等于x(>= x)**的元素,返回指向该元素的指针(vector则返回迭代器)。若所有元素都小于x,则返回尾后指针a + n。- 求数组下标:
int pos = lower_bound(a, a + n, x) - a;(若pos == n说明全数组没有>= x的数)。
- 求数组下标:
upper_bound(a, a + n, x):在半开区间[a, a + n)中二分查找**第一个严格大于x(> x)**的元素,返回指向该元素的指针;若不存在则返回a + n。- 求数组下标:
int pos = upper_bound(a, a + n, x) - a;。
- 求数组下标:
- 考场秒杀推论:在升序数组
a[0..n-1]中,数值恰好等于x的元素总个数,一行代码即可在 内算出:C++1 行int count_x = upper_bound(a, a + n, x) - lower_bound(a, a + n, x);
💡 考场黄金法则(背诵直接套用):
- 【缩界定中点口诀——看见
l = mid必加 1】:使用while (l < r)写整数二分时,先想清楚满足条件时是往左缩(r = mid配l = mid + 1)还是往右缩(l = mid配r = mid - 1);只要代码里写了r = mid,中点一律写l + (r - l) / 2;只要代码里写了l = mid,中点必须加 1 写成l + (r - l + 1) / 2!- 【收敛必验真 + STL 边界口诀】:
while (l < r)结束仅代表区间收敛到唯一候选点l,若原数组可能不存在合法解,最后一步必须检验a[l]是否满足条件;STL 中lower_bound找首个>= x,upper_bound找首个> x,两者做差即为有序数组中x的出现次数!
🔍 二、 具象代码与数据推演(有举例)
示例:在含重复元素的有序数组中同时定位 5 的左边界与右边界
设升序数组 int a[8] = {1, 3, 5, 5, 5, 7, 9, 11};,我们要分别求出数值 5 首次出现的下标(左边界)与最后一次出现的下标(右边界),并测试查找不存在数值 6 时的安全防呆表现:
#include <iostream>
using namespace std;
int a[8] = {1, 3, 5, 5, 5, 7, 9, 11};
// 模板一:查找第一个 >= x 的位置(检验是否等于 x 即得首次出现下标)
int find_first(int n, int x) {
int l = 0, r = n - 1;
while (l < r) {
int mid = l + (r - l) / 2; // 搭配 r = mid,向下取整不加 1
if (a[mid] >= x) {
r = mid;
} else {
l = mid + 1;
}
}
return (a[l] == x) ? l : -1;
}
// 模板二:查找最后一个 <= x 的位置(检验是否等于 x 即得末次出现下标)
int find_last(int n, int x) {
int l = 0, r = n - 1;
while (l < r) {
int mid = l + (r - l + 1) / 2; // 搭配 l = mid,向上取整必加 1
if (a[mid] <= x) {
l = mid;
} else {
r = mid - 1;
}
}
return (a[l] == x) ? l : -1;
}
int main() {
cout << "First index of 5: " << find_first(8, 5) << endl;
cout << "Last index of 5: " << find_last(8, 5) << endl;
cout << "First index of 6: " << find_first(8, 6) << endl;
return 0;
}分步指针收敛与内存状态推演表(以目标值 x = 5 为例)
| 调用函数 | 迭代轮次 | 当前闭区间 [l, r] |
计算出的 mid |
a[mid] 与条件判定 |
执行缩界动作 | 缩界后新区间 |
|---|---|---|---|---|---|---|
find_first(8, 5) |
第 1 轮 | [0, 7] |
0 + (7-0)/2 = 3 |
a[3] = 5 >= 5(真) |
r = mid = 3 |
[0, 3] |
find_first(8, 5) |
第 2 轮 | [0, 3] |
0 + (3-0)/2 = 1 |
a[1] = 3 >= 5(假) |
l = mid + 1 = 2 |
[2, 3] |
find_first(8, 5) |
第 3 轮 | [2, 3] |
2 + (3-2)/2 = 2 |
a[2] = 5 >= 5(真) |
r = mid = 2 |
[2, 2](退出) |
find_last(8, 5) |
第 1 轮 | [0, 7] |
0 + (7-0+1)/2 = 4 |
a[4] = 5 <= 5(真) |
l = mid = 4 |
[4, 7] |
find_last(8, 5) |
第 2 轮 | [4, 7] |
4 + (7-4+1)/2 = 6 |
a[6] = 9 <= 5(假) |
r = mid - 1 = 5 |
[4, 5] |
find_last(8, 5) |
第 3 轮 | [4, 5] |
4 + (5-4+1)/2 = 5 |
a[5] = 7 <= 5(假) |
r = mid - 1 = 4 |
[4, 4](退出) |
程序标准输出:
First index of 5: 2
Last index of 5: 4
First index of 6: -1请重点品味 find_last(8, 5) 的第 3 轮(区间 [4, 5]):如果当时忘记加 1 写了 mid = (4 + 5) / 2 = 4,由于 a[4] = 5 <= 5 为真,执行 l = mid = 4 后区间依然停留在 [4, 5],程序当场就会卡死在这里!而查找不存在的 6 时,find_first(8, 6) 会收敛到第一个 >= 6 的位置 l = 5(a[5] = 7),全靠末尾 a[l] == 6 的验真守门员将其拦截并返回 -1!
⚡ 三、 考场高频避坑指南(正误辨析)
在 GESP 五级客观题与 CSP-J 初赛/复赛中,以下三个二分陷阱每年都在批量收割粗心分:
❌ 易错点 1:退出 while (l < r) 后不验真,把“分界替身”当成合法解!
- 错误写法:要求找数组中第一个
>= x的元素值,写完while (l < r)后直接无脑cout << a[l];。 - 为什么错:设数组为
[1, 3, 5, 7](下标0..3),查询x = 100。在l = 0, r = 3的闭区间内,每次a[mid] >= 100都为假,不断执行l = mid + 1,最终l被一路推到右端点l = r = 3被迫退出循环!此时a[3] = 7根本不满足>= 100(整段区间全为false)! - 正确规范:二分收敛到
l == r之后,只要题目存在“无解”的可能,必须补上一句终极检验(如if (a[l] >= x)或if (a[l] == x));若直接用lower_bound(a, a + n, x),则必须先判断返回下标pos < n才能解引用读取a[pos],否则访问a[n]必越界!
❌ 易错点 2:在无序数组上强行二分,或对非随机访问容器调全局 std::lower_bound!
- 错误认知:“只要把数据塞进容器里,调
std::lower_bound(c.begin(), c.end(), x)就一定是 !” - 为什么错:
- 单调性铁律:二分查找(及
lower_bound/upper_bound)要求区间关于判定条件严格具备二段单调性;对未排序的乱序数组直接二分,每次折半可能会把真正包含目标值的那一半直接当废品扔掉,算出完全错误的荒谬结果; - 迭代器退化陷阱:对于
std::set或std::map(底层是红黑树,迭代器不支持 随机跳跃+ k),如果误写成全局函数std::lower_bound(s.begin(), s.end(), x),虽然比较次数是 ,但移动树迭代器需要一步步++走过节点,单次查询时间复杂度会惨烈退化为线性 导致 TLE!
- 单调性铁律:二分查找(及
- 正确规范:无序数组必须先耗费
sort排好序再做多次 二分查询;对于set/map,必须调用其自带的成员函数s.lower_bound(x),才能享受真正的 树上查找!
❌ 易错点 3:负数区间二分时混用 / 2 与 >> 1!
- 底层差异:当二分边界
l, r可能包含负数(如值域在 上二分答案)时,C++ 的整数除法(l + r) / 2是向零取整(例如(-3) / 2 == -1),而算术右移(l + r) >> 1是严格的向下取整(例如(-3) >> 1 == -2)! - 正确规范:如果直接套用
int mid = l + (r - l) / 2;与int mid = l + (r - l + 1) / 2;,因为始终满足r > l,所以r - l永远是正整数!正整数除以2无论用/ 2还是>> 1都严格等价于纯粹的向下取整——这正是l + (r - l) / 2写法既防溢出、又通杀正负数区间的双重神仙优势!
📝 四、 真题实战演练与精析(有例题:3 道)
【例题 1 · 单选题】(GESP 五级 / CSP-J 初赛阅读程序:死循环定位与比较次数推演)
题目:给定升序整型数组 int a[8] = {2, 4, 6, 6, 6, 9, 12, 15};,现欲在下标区间 l = 0, r = 7 中查找最后一个小于等于 7 的元素下标。两位同学分别写出了如下代码片段:
// 代码甲:
int l = 0, r = 7;
while (l < r) {
int mid = l + (r - l) / 2;
if (a[mid] <= 7) l = mid;
else r = mid - 1;
}
// 代码乙:
int l = 0, r = 7;
while (l < r) {
int mid = l + (r - l + 1) / 2;
if (a[mid] <= 7) l = mid;
else r = mid - 1;
}针对上述输入数组 a[0..7],关于代码甲与代码乙运行结果的判断,完全正确的是( )
- A. 代码甲与代码乙都能正常结束,且最终均得到
l = 4 - B. 代码甲能正常结束但停在错误的
l = 3;代码乙正常结束得到l = 4 - C. 代码甲会在
l = 3, r = 4处陷入无限死循环;代码乙执行 3 次if元素比较后正常结束,得到l = 4 - D. 代码甲与代码乙都会陷入无限死循环,因为
else分支应当写成r = mid
🔍 答案与逐项排除解析:
- 正确答案:C
- 解析过程:
- 追踪代码甲(
l = mid误配向下取整l + (r - l) / 2):- 第 1 轮:
l = 0, r = 7➔mid = 0 + 7 / 2 = 3,a[3] = 6 <= 7为真,执行l = 3,区间变为[3, 7]; - 第 2 轮:
l = 3, r = 7➔mid = 3 + 4 / 2 = 5,a[5] = 9 <= 7为假,执行r = 5 - 1 = 4,区间缩至相邻双元素[3, 4]; - 第 3 轮:
l = 3, r = 4➔mid = 3 + 1 / 2 = 3,a[3] = 6 <= 7为真,执行l = mid = 3!区间依然是[3, 4],后续每一轮都重复mid = 3 -> l = 3,彻底卡死在l = 3, r = 4无限死循环(排除 A、B)!
- 第 1 轮:
- 追踪代码乙(
l = mid正确配向上取整l + (r - l + 1) / 2):- 第 1 轮:
l = 0, r = 7➔mid = 0 + 8 / 2 = 4,第 1 次比较a[4] = 6 <= 7为真,l = 4,区间变为[4, 7]; - 第 2 轮:
l = 4, r = 7➔mid = 4 + 4 / 2 = 6,第 2 次比较a[6] = 12 <= 7为假,r = 5,区间变为[4, 5]; - 第 3 轮:
l = 4, r = 5➔mid = 4 + 2 / 2 = 5,第 3 次比较a[5] = 9 <= 7为假,r = 4,区间变为[4, 4],l < r不再成立,循环干净利落退出,精准锁定下标l = 4(排除 D,锁定 C)!
- 第 1 轮:
- 追踪代码甲(
【例题 2 · 判断题】(GESP 五级考纲概念辨析:lower_bound 与 upper_bound 边界行为)
题目:设整型数组 int a[6] = {10, 20, 20, 20, 30, 40}; 已按升序排列。在 C++ 中执行表达式 upper_bound(a, a + 6, 25) - lower_bound(a, a + 6, 25),由于数组中并不存在元素 25,两个函数内部查找失败均会返回尾后指针 a + 6,故相减结果为 0。( )
🔍 答案与反例证明:
- 结论:错误(×)
- 辨析证明:
- 虽然相减的最终数值确实是
0(因为数组中25出现了0次),但题干中**“两个函数内部查找失败均会返回尾后指针a + 6”的因果解释是完全错误的**! lower_bound(a, a + 6, 25)的定义是返回第一个>= 25的元素地址,在{10, 20, 20, 20, 30, 40}中,第一个>= 25的元素是下标为4的30,故返回a + 4(绝非a + 6!只有查询值比最大值40更大,如查50时才会返回a + 6);- 同理,
upper_bound(a, a + 6, 25)返回第一个> 25的元素地址,同样指向下标为4的30,返回a + 4。两者相减为(a + 4) - (a + 4) = 0。切记不要把lower_bound误解为“找不到相等值就返回end()”!
- 虽然相减的最终数值确实是
【例题 3 · 微代码实战】(GESP 五级 / CSP-J 复赛经典模板:有序序列元素首末区间定位)
题目描述:给定一个长度为 ()且已按非严格递增(升序,可能含重复元素)排好序的整数序列 (),以及 ()次独立查询。每次查询给出一个整数 ,请你手写左、右边界二分查找算法,输出 在序列中第一次出现的位置编号与最后一次出现的位置编号(位置编号从 开始计数);如果序列中不存在 ,则输出 -1 -1。
输入格式: 第一行包含两个正整数 和 ,分别表示序列长度与查询次数。 第二行包含 个升序排列的整数 。 接下来 行,每行包含一个待查询整数 。
输出格式:
输出共 行,每行两个整数(以空格分隔),表示对应查询值 的首次与末次位置编号,不存在则输出 -1 -1。
💡 算法建模与避坑要点:
- 复杂度刚需:,若每次用
for循环线性扫描找首尾,最坏复杂度为 必超时;使用左右边界双二分,每次查询仅需 次比较,总复杂度 轻松秒杀; - 模板对仗工整:
find_left用r = mid配l + (r - l) / 2锁定首个>= x的下标;若它都不等于x,说明全数组根本没有x,直接输出-1 -1无需再跑右二分;否则调用find_right(用l = mid配l + (r - l + 1) / 2)锁定末个<= x的下标即可!
#include <iostream>
using namespace std;
const int MAXN = 100005;
int a[MAXN];
// 左边界二分:查找第一个 >= x 的下标(1-based)
int find_left(int n, int x) {
int l = 1, r = n;
while (l < r) {
int mid = l + (r - l) / 2;
if (a[mid] >= x) {
r = mid;
} else {
l = mid + 1;
}
}
return (a[l] == x) ? l : -1;
}
// 右边界二分:查找最后一个 <= x 的下标(1-based)
int find_right(int n, int x) {
int l = 1, r = n;
while (l < r) {
int mid = l + (r - l + 1) / 2;
if (a[mid] <= x) {
l = mid;
} else {
r = mid - 1;
}
}
return (a[l] == x) ? l : -1;
}
int main() {
int n, q;
cin >> n >> q;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
while (q--) {
int x;
cin >> x;
int first_pos = find_left(n, x);
if (first_pos == -1) {
cout << "-1 -1" << endl;
} else {
cout << first_pos << " " << find_right(n, x) << endl;
}
}
return 0;
}- 输入样例:
Code5 行
8 3 1 3 5 5 5 7 9 11 5 6 11 - 输出样例:
(样例解释:序列从Code3 行
3 5 -1 -1 8 81开始编号,5连续出现在第3、4、5号位置,故首末位置为3 5;6在序列中不存在,左边界收敛至第6号位置元素7 != 6,直接返回-1 -1;11仅在末尾第8号位置出现一次,首末位置均为8 8。)
所有代码开源上传至 GitHub:yummy-code 仓库 · GESP 专题站:GESP WIKI
欢迎加入:C++ GESP/CSP 考级答疑群(688906745) 与 Java/Python交流群(982860385),点击可直接加群。
猜你想读 · 相关文章推荐
【GESP/CSP考点精讲】GESP四级/五级 / CSP-J 必背:递推 vs 递归——如何手画“递归调用树”秒杀初赛阅读程序题?
为什么在考场上遇到一句看似简单的 return f(n - 1) + f(n - 2);,有些同学在脑子里绕了三层就彻底“死机”,完全算不清函数到底被调用了多少次?为什么仅仅把 cout << n; 放在递归调用语句的前面和后面,打印出来的数字顺序就会发生天翻地覆的“逆...
【GESP/CSP考点精讲】GESP五级 / CSP-J 必背:从 O(2^n) 到 O(n) 的奇迹——重叠子问题与记忆化搜索
为什么一段只有 5 行的斐波那契递归代码 return fib(n - 1) + fib(n - 2);,当输入 n = 10 时瞬间出解,一旦输入 n = 45 就会触发超过 22 亿次函数调用,把评测机死死卡在 TLE(运行超时)?更神奇的是,为什么在不改变递归主体...
【GESP/CSP考点精讲】GESP五级 / CSP-J 必背:分治思想与归并排序(Merge Sort)——顺手秒杀“逆序对”统计
当题目给出的数据规模从 n = 1000 跃升到 n = 10^5 时,无论是冒泡排序、直接插入排序,还是用双重 for 循环暴力枚举统计“逆序对”,运算次数都会瞬间飙升至 (n(n-1)/2) ≈ 5 × 10^9 次,在 1 秒时限面前毫无悬念地触发 TLE(运行超...
OneCoder
一个中年人的自留地,记录学习 C++、GESP/NOI、Java、Python 与算法架构的心得体会。本站唯一网址:coderli.com

