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

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

给你一个仅由整数组成的有序数组，其中每个元素都会出现两次，唯有一个数只会出现一次。

请你找出并返回只出现一次的那个数。

你设计的解决方案必须满足 O(log n) 时间复杂度和 O(1) 空间复杂度。

这道题就不用O(N)的那个位运算了，必须使用二分。

我们可以观察到，在这样一个特殊的有序数组中，几乎必然的会出现奇数个数字，而当我们二分的时候，如果查找到了对应我们需要的唯一的数字，那么他的左右边必然和他不相等，否则，必然有且仅有一个数字是相等的。

而是哪一边的数字？我们可以通过观察得到，如果数字的下标为偶数，此时如果它左边的数字和他相等，那么出现的唯一的数字是出现在左侧的，如果右边相等，则是出现在右侧，如果为奇数，则是反过来。

代码如下：``

func singleNonDuplicate(nums []int) int {
    l, r := 0, len(nums) - 1
    for l < r {
        mid := (l + r) / 2
        if nums[mid] == nums[mid ^ 1] {
            l = mid + 1
        } else {
            r = mid
        }
    }
    return nums[r]
}