CSP-J 2023 第一轮 第 35 题：寻找被移除的元素：③处应填

题目

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;
}

③处应填（ ）

选项

• A. left=mid+1
• B. right=mid-1
• C. right=mid
• D. left=mid

答案

C

题解

选 C．right = mid。

这里用二分查找，寻找第一个不符合连续规律的位置。数组下标从 0 开始，如果没有缺失，应该满足： ``cpp nums[mid] == nums[0] + mid ``

• 如果相等，说明 mid 及其左边没有缺失，应继续查找右侧，即 left = mid + 1。
• 如果不相等，说明缺失发生在 mid 之前，mid 本身也可能就是第一个不符合规律的位置，因此要保留它，令 right = mid。

例如数组 [3, 4, 6, 7] 中，第一个不符合规律的位置是下标 2：实际为 6，应为 5。如果此时 mid = 2，使用 right = mid - 1 就会把目标位置排除，所以③应填 right = mid。