LeetCode
剑指Offer 53-Ⅱ.o~n-1中缺失的数字
一个长度为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
解法：二分查找
解题思路：
因为题目要求我们找到0~n-1中缺失的那一个数字，因此我们可以用二分法来找这一个数字,二分的条件为
- 当
mid<nums[mid]时，说明前面有数字缺失了，缺失的数字就在(left,mid)中，mid也可能是(比如说[0,2],中间数字mid=1就是那个缺失的数字)
- 当
mid=nums[mid]时，说明前面没有数字缺失，缺失的数字就在(mid+1,right)上，mid不可能是
代码如下：
class Solution {
public int missingNumber(int[] nums) {
int len = nums.length;
int left = 0;
int right = len;
while(left<right)
{
int mid=(left+right)>>1;
if(mid<nums[mid])
right=mid;
else
left=mid+1;
}
return left;
}
}
时间复杂为O(log2N)
空间复杂度为O(1)
其实刚才我直接遍历查找发现效率是一样的，可能是样本中nums的长度太短，导致效率没啥区别
