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

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

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

如果不考虑时间复杂度要求的话，最简单的就是以步长为2进行遍历，也可以用点位运算把整个数组全异或一边，最后的结果就是答案了。

int singleNonDuplicate(int* nums, int numsSize) {
    for (int i=0; i<numsSize-1; i+=2)
    {
        if (nums[i] != nums[i+1]) return nums[i];
    }
    return nums[numsSize-1];
}

int singleNonDuplicate(int* nums, int numsSize) {
    int ans=0;
    for (int i=0; i<numsSize; i++)
        ans ^= nums[i];
    return ans;
}

不过这题目真正需要思考的地方在于怎么把时间复杂度降到O(logn)。很容易想到和二分有关。因为数据是有序的，所以假设只出现一次的元素位于下标x，那么对于x左边的偶数下标y，一定有nums[y]=nums[y+1]。而对于x右边的奇数下标y，一定有nums[y]=nums[y+1]。

所以我们根据nums[y]=nums[y+1]的y是奇数还是偶数就可以知道x是在y的左边还是右边了。

class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        int len = nums.size();
        int l=0, r=len;
        while (l != r)
        {
            int mid=(l+r)/2;
            if (mid!=0 && nums[mid] == nums[mid-1])
            {
                if (mid%2) l=mid+1;
                else r=mid;
            }
            else if (mid!=len-1 && nums[mid] == nums[mid+1])
            {
                if (mid%2) r=mid;
                else l=mid+2;
            }
            else return nums[mid];
        }
        return nums[l];
    }
};