0 ~ n-1 中缺失的数字（剑指Offer 53-II）

题目

一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。

示例

输入: [0,1,3] 输出: 2

输入: [0,1,2,3,4,5,6,7,9] 输出: 8

限制

1 <= 数组长度 <= 10000

算法

遍历法

export const missingNumber_1 = (nums) => {
	for (let i = 0; i < nums.length; i++) {
		if (i !== nums[i]) {
			return i;
		}
	}
	return nums[nums.length - 1] + 1;
};

二分查找

对于题目排序数组的搜索问题应该想到使用二分查找

在不缺失的情况下，数组中的第i项的值应等于下标i，所以我们需要查找的是缺失数组（下标i的位置的值是i-1）的第一项

二分查找的条件：

• 当nums[mid]===mid时，缺失数组第一项一定在中点后面，即缺失数组的第一项一定在[mid+1, end]
• 当nums[mid]!==mid时，缺失数组第一项一定在中点前面，即缺失数组的第一项一定在[start, mid-1]

跳出循环的条件时start > end，即start指向了缺失数组的第一项、end指向了不缺失的数组的最后一项；当不满足start <= end的情况，在上一轮循环中一定是start和end指向了同一个位置，且发生了两种情况中的一种：

• start和end都指向了位置i且nums[i]===i，所以下一个位置i+1是缺失数组的第一项，此时start+1，条件不成立，返回start
• start和end都指向了位置i且nums[i]!==i，所以现在这个位置i是缺失数组的第一项，此时end-1，条件不满足，返回start

export const missingNumber = (nums) => {
	let start = 0,
		end = nums.length - 1;
	let mid = ~~((start + end) / 2);
	while (start <= end) {
		mid = ~~((start + end) / 2);
		if (nums[mid] === mid) start = mid + 1;
		if (nums[mid] !== mid) end = mid - 1;
	}
	return start;
};