数组中元素[1,1,2,3,3,4,4,8,8]，只有一个元素出现一次，其余出现两次，这里题目要求使用时间复杂度O(logn) 空间复杂度O(1),这里显而易见的方法是使用O(n) O(1)

class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        int res = 0;
        for(int i = 0;i < nums.size();i++)
            res ^= nums[i];
        
        return res;
    }
};

运行效率:

Runtime: 8 ms, faster than 90.08% of C++ online submissions for Single Element in a Sorted Array.
Memory Usage: 11 MB, less than 68.56% of C++ online submissions for Single Element in a Sorted Array.

另一种解决方法：

class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        if(nums.size() == 1) return nums[0];
        
        for(int i = 0;i < nums.size();i+=2)
        {
            if(i == nums.size() - 1)
                return nums[nums.size() - 1];
            
            if(nums[i] != nums[i+1])
                return nums[i];
        }
        
        return 0;
    }
};

如何使用O(logn)时间复杂度解决这个问题呢？二分查找如何查询呢？

class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        int left = 0,right = nums.size() - 1;
        while(left < right)
        {
            int mid = left + (right-left)/2;
            if(nums[mid] == nums[mid^1])
                left = mid + 1;
            else 
                right = mid;
        }

        return nums[left];
    }
};

一个详细的解释