题目链接：https://leetcode.cn/problems/single-element-in-a-sorted-array/description/
思路
题目中要求了复杂度为$O(\log N)$，所以不能用线性扫描的方法，还是只能用二分法。其实刚拿到这题是没什么思路的，但看了一下题解的提示，知道了因为这个单独元素的插入，会破坏原始的元素重复的规律：
- 在没有这个单独的元素前，始终是偶数位=奇数位，如此重复下去，比如[1,1,3,3,5,5]，其中每组两个重复元素11，33，55，对应的索引分别为01，23，45，都是左边为偶数索引，右边为奇数索引
- 但是在插入了这个单独的元素后，这种规律被打破，比如[1,1,2,3,3,5,5]，这样一来，每组两个重复元素对应索引就变成了01，34，56，可以发现，在这个单独元素的左边，规律还是保持不变，左边为偶右边为奇，但在这个元素的右边，就变成了每组左边索引为奇，右边为偶
可以利用这个规律来进行求解，梳理一下就是：
假设mid落在单独元素的左边：
- 如果mid为奇数，那么一定满足nums[mid] == nums[mid - 1]
- 如果mid为偶数，那么一定满足nums[mid] == nums[mid + 1]
假设mid落在单独元素的右边：
- 如果mid为奇数，那么一定满足nums[mid] == nums[mid + 1]
- 如果mid为偶数，那么一定满足nums[mid] == nums[mid - 1]
- 假设mid刚好落在单独元素的位置，那么它左右两边的数字都和它不相等
因此我们可以取case1来作为我们的判断条件，如果满足，就说明mid靠左了，要从左边缩短区间，取l = mid + 1（因为满足了相等的条件，那说明此刻mid也不是我们要找的答案，因此可以把它本身也排除掉，取mid + 1），如果不满足，那就说明mid要么刚好落在这个单独元素的位置，要么落在了单独元素的右边，要从右边缩短区间，取r = mid，因为有可能刚好落在这，所以不能把mid本身给排除掉，还是要直接取mid，重复以上循环，直到l ≥ r时，跳出，返回nums[l]
反思
- 这道题里我们取的是左开右闭的区间，左边要把mid给排除掉，但右边不要（大前提：我们的操作对象全部是整数，所以实际操作时用+1）
- 直接写上面的判断语句会非常麻烦，这里有个巧思是用异或操作，当奇数时，我们要判断mid - 1，当偶数时，我们要判断mid + 1，异或刚好能实现这个操作（二进制里，奇数最后一位一定为1，偶数最后一位一定为0，要实现分别-1和+1，异或能够实现，相同为0，相异为1，且和1进行运算，只改变最后一位，不会涉及到进位退位的问题）
结果
0ms 100%, 24.41MB 29.74%
