代码解析：完善程序-1

程序原理（为什么能二分）

  • 原本有一个公差为 1 的长度为 n+1 的等差序列：
    设首项为 S，完整序列应为：S, S+1, S+2, ..., S+n。
  • 现在移除了其中一个元素，得到长度为 n 的严格递增数组 nums。
  • 若移除的是首或尾，剩下的 n 个数仍然是连续的（公差仍为 1），此时数组内部无“断点”；否则会在被移除位置形成一个首次不连续点（从那一位开始都比“应有值”大 1）。
  • 因此存在一个单调性质：令“应有值”定义为 expect(i) = nums[0] + i
    • 若缺的是中间第 k 个应有元素（值为 S+k），则：
      • 对 i < k：nums[i] == expect(i)（完全吻合）
      • 从 i = k 起：nums[i] == expect(i) + 1（开始偏大 1）
    “是否满足 nums[i] == nums[0] + i” 在下标上是先真后假的单调布尔序列，能用二分找到第一个为假的位置。

找到这个“第一个不满足”的下标 left 后：

  • 若数组内部从未出现不满足（即始终连续），就把它判定为“缺首或缺尾；数组仍连续”，不输出具体缺值；
  • 若出现不满足，则缺失值就是“该处应有的值”=nums[0] + left。

每个空的原因

① nums[0]

  • 语义：用数组首元素当作等差序列的基准首项（因为我们不知道 S，但在未断点之前，nums[i] 应等于 nums[0] + i）。
  • 对比关系：nums[mid] == mid + nums[0] 就是在判断“到 mid 这一段是否仍连续无缺口”。

② left = mid + 1;

  • 若 nums[mid] == nums[0] + mid，说明到 mid 位置为止一切正常，缺口（如果存在）只能在右侧；
    因此把搜索区间推进到右半边。

③ right = mid;

  • 若 nums[mid] != nums[0] + mid，说明从 mid（含）开始已出现偏差，缺口的第一个位置不可能在右边，只能在左侧或就是 mid 本身；
    因此收缩右端到 mid 保留该点继续查找“第一个不满足”。

④ left + nums[0]

  • 当循环结束时，left 指向第一个不满足位置。该位置“应有值”是 nums[0] + left，也就是被移除的真正数值（如果确有缺口）。
  • 若数组内部无缺口（缺的是首或尾），二分会把 left 推到 n-1，此时返回的也是“该位置应有值”，用于做哨兵判断（见⑤）。

⑤ nums[n-1]

  • 判“连续”的策略：如果内部无缺口（即缺的是首或尾），整个数组满足 nums[i] == nums[0] + i，最终 left == n-1，函数返回 nums[0] + (n-1)；
    但这恰好等于当前数组的最后一个实际值 nums[n-1]。
  • 因而用 missing_number == nums[n-1] 作为**“数组仍连续”的判据**，打印 "Sequence is consecutive"；否则打印真正的缺失值。

代码分析：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#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 + nums[0]) {   // ① 前半段连续
            left = mid + 1;                 // ② 去右边找
        } else {                             // 发生偏差的第一个位置在左侧（含mid）
            right = mid;                    // ③ 去左边收缩
        }
    }
    // 此时left是“第一个不满足 nums[i] = nums[0] + i”的位置（若不存在，则left=n-1）
    return left + nums[0];                  // ④ 缺失的就是应在left处的值
}

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 == nums[n-1]) {      // ⑤ 没有内部缺口（缺首或缺尾），数组仍连续
        cout << "Sequence is consecutive" << endl;
    } else {
        cout << "Missing number is " << missing_number << endl;
    }
    return 0;
}
Previous Topic
Back to Lesson
Next Topic