剑指Offer刷题记录，第五题。
剑指 Offer 53 - II. 0～n-1中缺失的数字（easy）
方法一：二分
思路：核心思想在于<mark>排序数组中的搜索问题，首先想到二分法解决</mark>，需要注意的是缺失的数字一定是右边子数组的第一个元素，如下图描述。图片源于
class Solution {
public int missingNumber(int[] nums) {
// 特例
if (nums == null || nums.length == 0) {
return -1;
}
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left)/2;
if (nums[mid] == mid) {
// 左半边是完整的，找右半边。
left = mid + 1;
}else {
// 左半边不完整，找左半边。
right = mid - 1;
}
}
return left;
}
}
时间复杂度：O(LogN), N为数组长度，二分查找时间复杂度为O(LogN)。
空间复杂度：O(1), 未使用额外空间。
查看29道真题和解析