0～n-1中缺失的数字

题目链接: https://leetcode-cn.com/problems/que-shi-de-shu-zi-lcof/

image.png

思路解题
有序数组查找，直接二分。

代码如下

class Solution {
    public int missingNumber(int[] nums) {
        int i = 0, j = nums.length - 1;
        while(i <= j) {
            int m = (i + j) / 2;
            if(nums[m] == m) i = m + 1;
            else j = m - 1;
        }
        return i;
    }
}

复杂度分析
时间复杂度：O(logN)。
空间复杂度：O(1)。