题目

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

示例 1:

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

示例 2:

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

题解

由于数组中元素已按递增排序，所以相当于在数组中查找到最小的索引与值不同的元素。对于排序数组中元素的查找，可以使用二分查找解决

思路

以缺失的元素target为分隔：

• 左侧：i < target，nums[i] = i
• 右侧：i > target，nums[i] != i

实现：

• 初始：left = 0，right = len(nums) - 1，mid = (left + right) / 2
• 循环执行：
• 如果nums[mid] = i，target位于[mid + 1, right]之间，left = mid + 1
• 如果nums[mid] != i，target位于[left, mid - 1]之间，right = mid - 1
• 直至left <= right，left即为target

代码

func missingNumber(nums []int) int {
	var left, right int = 0, len(nums) - 1
	for left <= right {
		mid := (left + right) / 2
		if nums[mid] == mid {
			left = mid + 1
		} else {
			right = right - 1
		}
	}
	return left
}