OneCoder Avatar
OneCodercoderli.com · 1022 篇博文
五级

C++ 算法考级专栏

🎨 视觉封面

【GESP/CSP考点精讲】GESP五级 / CSP-J 必背:二分查找为什么会死循环?mid=(l+r)/2 与 (l+r+1)/2 终极判定指南

📅 2026-11-16·✍️ OneCoder·计算中...·⏱️ 33 分钟

算法竞赛圈流传着一句经典的自嘲:“二分查找思路只需十秒钟,调试边界死循环却要两小时!”为什么明明只是在一个有序数组里折半找数,有的时候写 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、-1 与 <=,一遇相邻区间当场死循环”:搞不清 while (l < r) 与 while (l <= r) 混用的后果,更不明白为什么分支里一旦出现 l = mid,中点公式不加 1 就会在 时原地踏步永不退出;
  2. “把二分狭隘理解为‘找某个相等的数’,面对重复元素束手无策”:一旦数组含有重复值(如 [2, 5, 5, 5, 8]),朴素找到 a[mid] == 5 就直接 return mid 的写法只能随机撞上其中一个 5,根本无法求出目标值的首次出现位置或出现总次数;
  3. “忽略‘全域无解’与 (l + r) 爆 int 两大隐蔽杀手”:二分缩界结束得到 l == r 后忘记检验该位置是否真正满足题目要求,或者在大值域(如 )下直接写 (l + r) / 2 导致有符号整数相加溢出变负数,瞬间引发数组越界 RE!

🧠 一、 核心原理深度拆解(有理论)

1. 二分的真正本质:不是“大海捞针找值”,而是“卡死 0/1 单调分界线”!

许多初学者之所以觉得二分条件千变万化,是因为把二分当成了“在数组里找等于 x 的元素”。事实上,二分查找的唯一本质,是在一段具有“二段单调性(0/1 单调性)”的区间上,用每次折半排除一半无效空间的手段,精准锁定左半段与右半段的交界点!

哪怕原数组包含大量重复元素,只要我们定义一个布尔判定性质 check(i),就能把整个区间映射为前半段全是一种状态、后半段全是另一种状态的“黑白分界带”:

Code15 行
====================================================================================
【二分本质:把含重复元素的有序数组映射为 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 检验两条分支是否都能让区间严格变短:

Code15 行
====================================================================================
【生死审判现场:当区间仅剩相邻两个元素 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);

💡 考场黄金法则(背诵直接套用):

  1. 【缩界定中点口诀——看见 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!
  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 时的安全防呆表现:

C++39 行
#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](退出)

程序标准输出:

Code3 行
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) 就一定是 !”
  • 为什么错:
    1. 单调性铁律:二分查找(及 lower_bound / upper_bound)要求区间关于判定条件严格具备二段单调性;对未排序的乱序数组直接二分,每次折半可能会把真正包含目标值的那一半直接当废品扔掉,算出完全错误的荒谬结果;
    2. 迭代器退化陷阱:对于 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 的元素下标。两位同学分别写出了如下代码片段:

C++15 行
// 代码甲:
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
  • 解析过程:
    1. 追踪代码甲(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)!
    2. 追踪代码乙(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)!

【例题 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。( )

🔍 答案与反例证明:

  • 结论:错误(×)
  • 辨析证明:
    1. 虽然相减的最终数值确实是 0(因为数组中 25 出现了 0 次),但题干中**“两个函数内部查找失败均会返回尾后指针 a + 6”的因果解释是完全错误的**!
    2. lower_bound(a, a + 6, 25) 的定义是返回第一个 >= 25 的元素地址,在 {10, 20, 20, 20, 30, 40} 中,第一个 >= 25 的元素是下标为 4 的 30,故返回 a + 4(绝非 a + 6!只有查询值比最大值 40 更大,如查 50 时才会返回 a + 6);
    3. 同理,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。

💡 算法建模与避坑要点:

  1. 复杂度刚需:,若每次用 for 循环线性扫描找首尾,最坏复杂度为 必超时;使用左右边界双二分,每次查询仅需 次比较,总复杂度 轻松秒杀;
  2. 模板对仗工整:find_left 用 r = mid 配 l + (r - l) / 2 锁定首个 >= x 的下标;若它都不等于 x,说明全数组根本没有 x,直接输出 -1 -1 无需再跑右二分;否则调用 find_right(用 l = mid 配 l + (r - l + 1) / 2)锁定末个 <= x 的下标即可!
C++52 行
#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 8
    (样例解释:序列从 1 开始编号,5 连续出现在第 3、4、5 号位置,故首末位置为 3 5;6 在序列中不存在,左边界收敛至第 6 号位置元素 7 != 6,直接返回 -1 -1;11 仅在末尾第 8 号位置出现一次,首末位置均为 8 8。)
看完题解去实战!OneCoder C++ 信奥远征闯关平台 (oi.coderli.com)
💡 OneCoder 资源指引

所有代码开源上传至 GitHub:yummy-code 仓库 · GESP 专题站:GESP WIKI

🤝 技术交流与答疑

欢迎加入:C++ GESP/CSP 考级答疑群(688906745) 与 Java/Python交流群(982860385),点击可直接加群。

📚

猜你想读 · 相关文章推荐

GESP 编程与算法 · 五级⏱️ 26 分钟

【GESP/CSP考点精讲】GESP四级/五级 / CSP-J 必背:递推 vs 递归——如何手画“递归调用树”秒杀初赛阅读程序题?

为什么在考场上遇到一句看似简单的 return f(n - 1) + f(n - 2);,有些同学在脑子里绕了三层就彻底“死机”,完全算不清函数到底被调用了多少次?为什么仅仅把 cout << n; 放在递归调用语句的前面和后面,打印出来的数字顺序就会发生天翻地覆的“逆...

阅读全文 →
GESP 编程与算法 · 五级⏱️ 31 分钟

【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 编程与算法 · 五级⏱️ 33 分钟

【GESP/CSP考点精讲】GESP五级 / CSP-J 必背:分治思想与归并排序(Merge Sort)——顺手秒杀“逆序对”统计

当题目给出的数据规模从 n = 1000 跃升到 n = 10^5 时,无论是冒泡排序、直接插入排序,还是用双重 for 循环暴力枚举统计“逆序对”,运算次数都会瞬间飙升至 (n(n-1)/2) ≈ 5 × 10^9 次,在 1 秒时限面前毫无悬念地触发 TLE(运行超...

阅读全文 →
OneCoder

OneCoder

一个中年人的自留地,记录学习 C++、GESP/NOI、Java、Python 与算法架构的心得体会。本站唯一网址:coderli.com

读者讨论与留言

共 0 条讨论
邮箱必填 · 支持 Markdown 格式与直接回复
💬 还没有读者留言,快来成为第一个讨论者吧!