540.有序数组中的单一元素

题目

给定一个只包含整数的有序数组，每个元素都会出现两次，唯有一个数只会出现一次，找出这个数。

示例 1:
输入: [1,1,2,3,3,4,4,8,8]
输出: 2

示例 2:
输入: [3,3,7,7,10,11,11]
输出: 10

注意: 您的方案应该在 O(log n)时间复杂度和 O(1)空间复杂度中运行。

方法（二分查找）

所给数组有序，考虑使用二分法。

单一的元素左右两边的特点为：

• m为偶数时，在单一元素左边，nums[m] == nums[m + 1]
• m为奇数时，在单一元素右边，nums[m] != nums[m + 1]

可以据此来进行二分的流程，但是注意：一定要保证mid为偶数

代码

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

注：二分查找

对于二分查找，要做到细节不出错，需要关注三件事：

• 左右边界
• 循环条件
• 如何进入下一步循环

第一种情况

左右边界是指，初始时left和right的取值，如果

left = 0 , right = nums.length - 1

则表明搜索范围是[left, right]这样一个闭区间

因此循环条件就应该写成：

while(left <= right)

即：当left==right时，由于是闭区间，因此当前的查找范围[left, right]里尚且有一个元素，应该再次进入循环，而不是退出

进一步考虑，进入下一步循环就应该写为：

left = mid + 1;
right = mid - 1;

因为当前mid位置已经查找过，下一步查找范围为闭区间[left, mid - 1]或者闭区间[mid, right]

第二种情况

但是，如果在初始化left和right时

left = 0, right = nums.length

则表明搜索范围是[left, right)这样一个左闭右开区间

因此循环条件就应该写成：

while(left < right)

因为，left==right时，区间[left, right)里已经没有元素，不应该再进入循环。

进一步考虑，进入下一步循环就应该写为：

left = mid + 1;
right = mid;

因为在mid位置查找过后，因为查找区间均为左闭右开区间，原查找区间为[left, right)，因此下一步查找范围为区间[left, mid)，或者区间[mid + 1, right)