GESP 五级 · GESP 202409 C++ 五级 第 13 题

根据下述二分查找法，在排好序的数组 $1, 3, 6, 9, 17, 31, 39, 52, 61, 79$ 中查找数值 $31$，循环 while (left <= right) 执行的次数为（ ）。

int binary_search(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size() - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (nums[mid] == target) {
            return mid;
        }
        else if (nums[mid] < target) {
            left = mid + 1;
        }
        else {
            right = mid - 1;
        }
    }

    return -1; // 如果找不到目标元素，返回-1
}

仔细审题，明确已知条件和所求目标，运用相关知识点逐项分析。

审题时注意题目要求（选正确还是选错误），避免因审题不清失分。涉及代码的题目要逐行分析变量变化。

【考点】二分查找｜循环边界控制｜数组操作

1. 考纲定位 本题考查 GESP 五级"高级算法与数据结构"模块中的二分查找实现细节。命题人专卡"循环条件与索引更新"的细微差别，90% 考生误以为只要找到就停，却忽略了 left <= right 的边界处理逻辑。

2. 解题思维 第 1 轮 mid=4(17<31)→left=5；第 2 轮 mid=7(52>31)→right=6；第 3 轮 mid=5(31==31)→返回。关键观察是循环条件 left <= right 保证搜索区间非空，每次更新后区间缩小一半，直到命中。这类题通法：手动模拟三到四轮，记录 mid 取值与区间变化，比背公式更可靠。

3. 陷阱拆解 A 误以为"找到即停"（忽略区间缩小过程）；B 按 mid=5 误判为两轮（整数除法导致 mid 偏小）；D 把边界条件 left < right 代入（会多一轮空转）。最阴险处：mid = left + (right - left) / 2 防溢出写法，看似复杂却直接决定每次跳过的索引，只背结论者必栽跟头。

4. 反命题思维 若改目标为 39，循环必多一次；若把条件写成 left < right，答案变 2；若 mid 更新漏 +1，直接死循环。记住：二分题永远先模拟，再套结论。