题目描述

一个长度为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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/que-shi-de-shu-zi-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路分析

• 这是排序数组查找元素的题目，对于排序数组，一般使用二分法，效率比较高。

• 二分查找，每次计算数组当前部分的中间元素，如果中间元素刚好是要找的，就结束搜索过程；如果中间元素小于所查找的值，那么左侧的只会更小，不会有所查找的元素，只需到右侧查找；如果中间元素大于所查找的值同理，只需到左侧查找。

• 二分查找

代码

    public int missingNumber(int[] nums) {
        int n = nums.length;
        int left = 0;
        int right = n - 1; 
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == mid) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return left;
    }

总结

• 二分查找解法的时间复杂度是 O(log n), 空间复杂度是O(1)

• 二分查找整体思路比较清晰，每一步都要清楚为什么这样写，不要跳步，更不能想当然。需要注意下列几个地方：

• 坚持每日一题，加油！