一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
示例:
输入: [0,1,2,3,4,5,6,7,9]
输出: 8

解题思路：

只包含0～n-1数字的数组是有序数组，如果数字没有缺失的话，必然存在数组的索引与数组的内容相等，这样的话，第一个出现缺失的点便是我们要查找的数据。

核心思想：我们可以将要查找的数组分成两个部分，左半部分和右半部分，我们先去查询左半部分，如果没有找到再去查找右半部分，最终肯定能够找出要查询的数据。

代码实现：

public class Solution_111 {
    private int res = -1;

    public int missingNumber(int[] nums) {
        findNum(nums, 0, nums.length - 1);
        return res;
    }

    private void findNum(int[] nums, int left, int right) {
        if (left < right && res == -1) {
            int mid = left + (right - left) / 2;

            findNum(nums, left, mid);
            findNum(nums, mid + 1, right);

            res = findNumItem(nums, left, right);
        }
    }

    private int findNumItem(int[] nums, int left, int right) {
        while (left <= right) {
            if (nums[left++] != left - 1) {
                return left - 1;
            }
        }
        return -1;
    }

    public int missingNumber2(int[] nums) {
        int index = 0;
        while (index < nums.length) {
            if (nums[index++] != index - 1) {
                return index - 1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        Solution_111 solution_111 = new Solution_111();
        int res = solution_111.missingNumber(new int[]{0, 1, 2, 3, 4, 5, 6, 7, 9});
        System.out.println(res);
    }
}