如何在百万级有序数组中查找首个缺失数字？

针对升序排列、从0开始的百万级数组，二分查找是兼顾时间与内存的最优方案，时间复杂度为O(log n)，空间复杂度仅O(1)，远优于线性遍历的O(n)时间消耗。

核心逻辑 #

正常情况下，数组的下标i应该对应元素值i（因为从0开始连续）。如果某个位置mid的元素值大于mid，说明首个缺失的数字一定在[0, mid]区间内；如果元素值等于mid，则说明前半部分无缺失，只需在右半部分继续查找。

具体实现步骤 #

1. 初始化左右指针：left = 0，right = len(arr) - 1
2. 初始化默认缺失值为数组长度n（对应极端情况：数组包含0到n-1所有数，缺失n）
3. 循环查找直到left > right：
   • 计算中间索引mid = (left + right) // 2
   • 若arr[mid] == mid：左半部分无缺失，将left移到mid + 1
   • 若arr[mid] > mid：缺失值在左半部分，更新缺失值为mid，将right移到mid - 1
4. 循环结束后返回缺失值

示例验证 #

以你提到的场景为例：数组在4380之后直接是4382。遍历到索引4380时，元素值等于下标，left会移到4381；此时mid=4381，元素值4382>4381，因此将缺失值设为4381，right移到4380，循环结束，返回4381，符合预期。

优势说明 #

• 时间：百万级数组的二分查找仅需约20次迭代（因为2^20≈100万），比线性遍历百万次快几个数量级
• 内存：全程仅使用几个指针变量，无需额外内存空间，完全适配大规模数组场景

内容的提问来源于stack exchange，提问作者Sambhav Khandelwal