剑指Offer刷题记录，第五题。

方法一：二分

思路：核心思想在于<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), 未使用额外空间。