二分法实现数组特定元素查找

题目链接-来源：力扣（LeetCode）

一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。

示例 1:

输入: [0,1,3]
输出: 2

思路：

我们可以很容易地将数组分为两部分，一部分是「缺失元素之前的部分」，该部分的特点是数组下标值即等于元素值；另一部分是「缺失元素之后的部分」，该部分的特点是数组下标值小于元素值。
我们只要找到「缺失元素之后的第一个元素」，将其减去 1 即可得到所需结果。借鉴前一题 helper() 函数的二分思路，二分缩小左边界的条件应该是 nums[m] = m，这样我们就能找到满足 nums[m] != m 的第一个元素。
时间复杂度：O(logn)
空间复杂度：O(1)

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int missingNumber(int[] nums) {
        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;
    }
}