GESP 五级 · GESP 202312 C++ 五级 第 9 题

下面 C++ 代码用于有序 list 的二分查找，有关说法错误的是（ ）。

int _binarySearch(vector<int> lst, int Low, int High, int Target)
{
    if (Low > High)
        return -1;
    int Mid = (Low + High) / 2;
    if (Target == lst[Mid])
        return Mid;
    else if (Target < lst[Mid])
        return _binarySearch(lst, Low, Mid - 1, Target);
    else
        return _binarySearch(lst, Mid + 1, High, Target);
}

int bSearch(vector<int> lst, int Val)
{
    return _binarySearch(lst, 0, lst.size(), Val);
}

这题考的是算法思想的辨析，别被递归函数名带偏，抓住‘子问题是否重叠’这个核心判据，就能一眼看出它只是分治递归，绝不是动态规划。

很多学生看到递归就下意识想动态规划，因为两者都涉及把大问题拆小。但关键在于：动态规划必须处理‘重叠子问题’，需要记忆化或填表；而本题每次递归处理的区间都是全新的，完全不重叠，中间也没任何数组存中间结果，所以它纯粹是分治。命题人就是利用这种‘递归=DP’的惯性思维挖坑，让你选D。

考纲定位

GESP五级《算法设计》模块，核心要求是区分分治、动态规划、回溯这三大思想。这道题把二分查找的代码扔出来，表面看是考STL或递归语法，实则是在考概念辨析——你能不能分清‘实现方式’和‘算法思想’的差别。

知识点人话解释

分治算法：把一个大问题拆成几个互不依赖的小问题，分别解决，最后把结果拼起来。比如排序里的快排、归并，查找里的二分。 动态规划：拆出来的小问题有重叠，同一个子问题会被算多次，所以得记下来（记忆化或填表），避免重复劳动。 递归：只是编程技术，函数自己调用自己；分治可以用递归实现，也可以用循环实现，递归不是算法分类。

命题人怎么挖坑

代码里函数名叫_binarySearch，一看就是二分查找。命题人故意把二分放在这里，因为二分是典型的分治，但又是纯递归实现，没有中间数组。学生容易犯两个错： 1. 看到递归就选动态规划（惯性联想）； 2. 把二分当成独立算法思想，忽略它属于分治家族。 这道题就是专门卡住‘只背术语、不辨本质’的考生。

思考心法：拿到题先想什么

1. 看函数调用：bSearch调_binarySearch，_binarySearch把区间[Low, High]拆成[Low, Mid-1]和[Mid+1, High]，两个子区间毫无交集，说明子问题不重叠。 2. 看有没有记忆化：代码里没有任何数组存中间结果，也没有memo或dp表，说明没有重复计算优化。 3. 看返回值：直接返回Mid或继续递归，没有‘合并’步骤（分治通常有合并，但查找类分治可以只有分解和解决），但这不影响它属于分治思想。 4. 结论：这是典型的分治递归实现，不是动态规划。

逐项分析（紧扣选项）

• A. 代码采用二分法实现有序list的查找：对。Mid = (Low+High)/2，根据目标值大小决定向左或向右递归，这就是二分法。
• B. 代码采用分治算法实现有序list的查找：对。区间被拆成两个互不依赖的子问题，分别求解，符合分治三要素（分解、解决、合并）。
• C. 代码采用递归方式实现有序list的查找：对。函数自己调用自己，直到Low > High终止。
• D. 代码采用动态规划算法实现有序list的查找：错。动态规划必须满足‘子问题重叠’且‘有记忆化/填表’。本题每次递归都是全新区间，没有重叠，也没有任何数组存中间结果，自然不是DP。

避坑：最容易错在哪

学生常把‘递归’和‘动态规划’画等号，因为两者都涉及‘拆小问题’。但递归只是实现手段，分治是思想；动态规划是另一种思想，要求子问题重叠。本题代码里没有任何dp数组或memo，也没有重复计算同一区间，所以D项明显错误。命题人就是想让你在A、B、C都正确的情况下，唯一错误的是D。

考频与趋势

在题库的分治算法考点中，2023年考了4题，2024年17题，2025年14题，2026年15题，呈现逐年上升趋势，说明分治思想是近年命题重点。而在动态规划考点里，2023年14题，2024年24题，2025年25题，2026年30题，同样是高频且持续升温。但二分查找单独作为一个考点，2023年仅4题，2024年9题，2025年7题，2026年5题，虽然2024年有小幅高峰，整体仍低于分治和动态规划。这说明命题人更倾向于把二分查找嵌入到分治或递归的语境中考查，而不是单独考二分。

预测

基于上述数据，未来GESP五级及CSP入门级更可能在‘算法思想辨析’类题目中继续加大分治与动态规划的区分度，例如给出一个看似递归但实际有重叠子问题的代码，让你判断是DP还是分治。二分查找作为基础工具，单独命题的概率会维持低位，更多作为干扰项出现在综合题中。暂无足够依据预测具体题型，但可以肯定的是，‘递归≠动态规划’这个坑还会反复挖。