https://leetcode-cn.com/problems/single-element-in-a-sorted-array/

解法1：二分法

题目中很明确的说了，需要O(logn)的算法，这简直就是二分的代名词。
二分的本质是需要去找一个性质，一半满足另一半不满足。
这个性质就是，相等的两个元素中的第一个的下表一定是偶数。
当你搜索到某个下标时，如果它是偶数，那就看它=它的下一个元素；如果它是奇数，那就它=它的前一个元素。
又根据异或的性质，偶数和1异或=该数+1，奇数和1异或等于该数-1。
即该数组的左端满足nums[mid]nums[mid^{1]，右端不满足，且要找的那个元素就是第一个满足nums[mid]!=nums[mid}1]的。
本题中，性质记作“nums[mid]nums[mid^1]”，要找第一个满足该条件的。

如果该条件得到满足，说明mid在后半段，右指针应该收缩到mid的位置，即使用二分法模板1。可得代码如下：

public int singleNonDuplicate(int[] nums) {
    int l = 0, r = nums.length-1;
    while(l < r) {
        int mid = l + r >> 1;
        if(nums[mid] != nums[mid ^1]) r = mid;
        else l = mid + 1;
    }
    return nums[r];
}

解法2：异或法

刚刚既然说到了异或，那么其实异或还有一个很有意思的性质：
a^a=0,0a=a
则有一个O(n)的算法：

public int singleNonDuplicate(int[] nums) {
    int res = 0;
    for(int a: nums) res ^= a;
    return res;
}

Just a joke！2022情人节快乐！