CSP-J 入门级 · CSP 2023 入门级第一轮 第 19 题

三、完善程序（单选题，每小题 3 分，共计 30 分）

1. (寻找被移除的元素)问题: 原有长度为 $n+1$ 公差为 $1$ 等差数列，将数列输到程序的数组时移除了一个元素，导致长度为 $n$ 的连续数组可能不再连续，除非被移除的是第一个或最后一个元素。需要在数组不连续时，找出被移除的元素。试补全程序。

#include <iostream>
#include <vector>
using namespace std;
int find_missing(vector<int>& nums) {
    int left = 0, right = nums.size() - 1;
    while (left < right){
        int mid = left + (right - left) / 2;
        if (nums[mid] == mid + ①) {
            ②;
        } else {
            ③;
        }
    }
    return ④;
}
int main() {
    int n;
    cin >> n;
    vector<int> nums(n);
    for (int i = 0; i < n; i++) cin >> nums[i];
    int missing_number = find_missing(nums);
    if (missing_number == ⑤) {
        cout << "Sequence is consecutive" << endl;
    }else{
        cout << "Missing number is " << missing_number << endl;
    }
    return 0;
}

1. ①处应填（ ） 2. ②处应填（ ） 3. ③处应填（ ） 4. ④处应填（ ） 5. ⑤处应填（ ）

这题本质是二分查找。拿到题先想：原序列 nums[i] 本该是 nums[0]+i，现在缺了一个，缺口前等式成立，缺口后整体右移一位。利用这个性质，在 left<right 时取 mid，若 nums[mid]==mid+nums[0] 说明缺口在右边，否则在左边。循环结束 left 指向缺失位置，缺失值就是 left+nums[0]。最后还要判断缺失的是首或尾时序列仍连续的特殊情况。

最易错在⑤处判断连续的条件。很多学生看到题目说‘除非被移除的是第一个或最后一个元素’，就以为只要 missing_number 等于 nums[n-1] 就是连续，其实逻辑反了：当序列连续时，二分过程会让 left 一直右移到 n-1，此时 missing_number = (n-1)+nums[0] = nums[n-1]，所以判断连续应该用 missing_number == nums[n-1]。另一处坑是③处，当 nums[mid] 不等于预期值时，缺口可能在 mid 本身，所以 right 必须取 mid 而不能取 mid-1，否则可能漏掉答案。还有①处一定要填 nums[0] 而不是 1，因为题目没说从 1 开始，而是从数组第一个元素开始偏移。

考点与命题视角

这道题考查的是一维数组的性质、等差数列的基本概念以及二分查找算法的应用。命题人喜欢在这种‘完善程序’的题型里挖坑：表面看是简单的二分，实则暗藏对边界条件的苛刻要求。他们喜欢考学生是否真正理解了‘连续’的定义，以及二分查找中 left 和 right 的更新逻辑。特别是当缺失的是首或尾元素时，序列依然连续，这种‘看似有缺口实则无缺口’的情况，就是命题人最爱设的陷阱。

核心概念：等差数列与偏移

原数组是长度为 n+1、公差为 1 的等差数列，即连续整数。假设第一个元素是 nums[0]，那么完整的序列应该是： nums[0], nums[0]+1, nums[0]+2, …, nums[0]+n。

移除一个元素后，数组长度变为 n。如果移除的是中间某个元素，那么在移除位置之前，元素值与下标的关系保持不变：nums[i] = nums[0] + i；而在移除位置之后，所有元素整体向后平移一位，相当于每个元素的值都比它‘应该’的值大了 1：nums[i] = nums[0] + i + 1。

这个‘偏移 1'的性质，就是二分查找的判据。我们只需要检查 nums[mid] 是否等于 mid + nums[0]。如果相等，说明 mid 及其左侧都是连续的，缺口一定在右侧；如果不相等，说明缺口在左侧（包括 mid 本身）。