53-II. 0～n-1中缺失的数字
1. 描述
一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
2. 例子
示例 1:
输入: [0,1,3]
输出: 2
示例 2:
输入: [0,1,2,3,4,5,6,7,9]
输出: 8
3. 限制
- 1 <= 数组长度 <= 10000
4. 题解
n = i_nums.size()
时间复杂度: O(n)
空间复杂度: O(1)
有序数组查找数据，自然是二分。如果不是有序的话，可以考虑归位法，即将每个数据放到与其下标一致的地方，时间复杂度为 O(n)。
class Solution
{
public:
// int missingNumber(vector<int>& nums)
int missingNumber(vector<int> &i_nums)
{
if(i_nums.front() == 1) return 0;
if(i_nums.back() == i_nums.size() - 1) return i_nums.size();
int lastCompleteIndex = 0, firstUncompleteIndex = i_nums.size() - 1;
while(lastCompleteIndex + 1 < firstUncompleteIndex)
{
int middle = lastCompleteIndex + ((firstUncompleteIndex - lastCompleteIndex) >> 1);
if(i_nums[middle] == middle) lastCompleteIndex = middle;
else firstUncompleteIndex = middle;
}
return lastCompleteIndex + 1;
}
};