题目描述
一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
题解
这道题目有两个比较直观的解，一个方法是从0开始顺序遍历数组，如果发现哪个位置不连续了，则找到这个数字。另一个方法是将0 ~ n-1 的和减去数组的和，得到的结果就是缺失的数字。这两种方法的时间复杂度都是O(n)。
其实时间复杂度为O(logn)的的二分法也是比较容易想到的，来看代码。
class Solution {
public int missingNumber(int[] nums) {
int left = 0, right = nums.length-1, mid;
while (left < right) {
mid = (left + right) >> 1;
// 说明没有问题，缺失的数字在mid右边
if (mid == nums[mid]) {
left = mid + 1;
}
// 说明缺失的数字在mid左边
else if (mid < nums[mid]) {
right = mid - 1;
}
}
// 最终缺失的数字要么在left左边，要么在left右边
if (left < nums[left])
return nums[left] - 1;
return nums[left] + 1;
}
}
