540 Single Element in a Sorted Array

Leetcode

You are given a sorted array consisting of only integers where every element appears exactly twice, except for one element which appears exactly once.

Return the single element that appears only once.

Your solution must run in O(log n) time and O(1) space.

Example 1:

Input: nums = [1,1,2,3,3,4,4,8,8]
Output: 2

Example 2:

Input: nums = [3,3,7,7,10,11,11]
Output: 10

在单个的数字的左边，每个奇数下标的数字等于下标减 1 的数字，每个偶数下标的数字等于下标加 1 的数字；在单个数字的右边相反。使用和 1 异或实现下标偶数加 1 奇数减 1 。当某下标的数字等于异或 1 下标的数字时说明单个数字在右边，反之单个数字为当前数字或在左边。使用左闭右开的二分查找，时间复杂度 o(log n)。

public int singleNonDuplicate(int[] nums) {
    int low = 0, high = nums.length-1;
    int mid, n;
    while(low<high){
        mid = (low+high)/2;
        n = mid ^ 1;
        if(nums[mid] == nums[n]){
            low = mid + 1;
        } else {
            high = mid;
        }
        
    }
    return nums[low];
}