题目：
给你一个仅由整数组成的有序数组，其中每个元素都会出现两次，唯有一个数只会出现一次。
请你找出并返回只出现一次的那个数。
你设计的解决方案必须满足 O(log n) 时间复杂度和 O(1) 空间复杂度。
示例 1:
输入: nums = [1,1,2,3,3,4,4,8,8]
输出: 2
示例 2:
输入: nums = [3,3,7,7,10,11,11]
输出: 10
提示:
- 1 <= nums.length <= 105
- 0 <= nums[i] <= 105
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/single-element-in-a-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解题思路：
【二分查找】
看到题目要求：解决方案必须满足 O(log n) 时间复杂度和 O(1) 空间复杂度，就会想到用过二分查找！但是二分条件一般是中间值和目标值相比较，这里一直卡在寻找目标值，自己没想出来，参考：@（彤哥来刷题）老师的思路：https://leetcode.cn/problems/single-element-in-a-sorted-array/solution/tong-ge-lai-shua-ti-la-er-fen-cha-zhao-b-x8dd/
题目中说了只有一个数出现一次，其他数出现两次，那么这个数组长度肯定为奇数，采用二分法缩小搜索范围，肯定会把数组分为一边是偶数个数，一边是奇数个数。且把单独数补上，例如[3,3,7,7,10,11,11]--> [3,3,7,7,10,10,11,11]，可以观察到[偶数下标，奇数下标]的数肯定相等。
那么具体的二分查找过程为：
- 初始化左右边界：left = 0，right = nums.length - 1，计算出mid = left + (right - left) / 2，循环条件是：left < right；
- 如果mid为偶数，由于数组下标是从0开始的，mid之前（包括mid）一共有奇数个数，mid后面有偶数个数，于是就判断nums[mid]与nums[mid+1]是否相等：
- 如果nums[mid] == nums[mid+1]，则说明后面剩余的数为奇数个了，则单独数出现在后面，即让left = mid +1;
- 如果nums[mid] != nums[mid+1]，则说明要么mid就为单独数，要么单独数出现在前面，即让right = mid。
- 如果mid为奇数，mid之前（包括mid）一共有偶数个数，mid后面有奇数个数，于是就判断nums[mid]与nums[mid-1]是否相等：
- 如果nums[mid-1] == nums[mid]，则说明单独数出现在后面，即让left = mid +1;
- 如果nums[mid-1] != nums[mid]，则说明要么mid为单独数，要么单独数出现在后面，即让right = mid。
- 循环结束条件：left == right，直接返回left 或者right即可。
java代码：
1 class Solution {
2 public int singleNonDuplicate(int[] nums) {
3 int left = 0, right = nums.length - 1;
4 while (left < right){
5 int mid = left + (right - left) / 2;
6 //mid为偶数，包括mid以及之前有奇数个数
7 if (mid % 2 == 0){
8 //mid和mid+1相等，表示单独数出现在后面
9 if (nums[mid] == nums[mid + 1]){
10 left = mid + 1;
11 }else{
12 //mid和mid+1不相等，表示单独数出现在前面
13 right = mid;
14 }
15 }else{
16 //mid为奇数，包括mid以及之前有偶数个数
17 //mid和mid-1相等，说明单独数出现在后面
18 if(nums[mid-1] == nums[mid]){
19 left = mid + 1;
20 }else{
21 //mid和mid-1不相等，说明单独数出现在前面
22 right = mid;
23 }
24 }
25 }
26 return nums[left];
27 }
28 }
java二分查找-异或：
异或：相同为0，不同为1，偶数异或相当于加1，奇数异或相当于减1。
1 class Solution {
2 public int singleNonDuplicate(int[] nums) {
3 int left = 0, right = nums.length - 1;
4 while (left < right){
5 int mid = left + (right - left) / 2;
6 //mid为偶数，包括mid以及之前有奇数个数
7 //mid和mid+1相等，表示单独数出现在后面
8 if (nums[mid] == nums[mid ^ 1]){
9 left = mid + 1;
10 }else{
11 //mid和mid+1不相等，表示单独数出现在前面
12 right = mid;
13 }
14 }
15 return nums[left];
16 }
17 }
python3代码-异或：
1 class Solution: 2 def singleNonDuplicate(self, nums: List[int]) -> int: 3 left, right = 0, len(nums) - 1 4 while left < right: 5 mid = left + (right - left) // 2 6 if nums[mid] == nums[mid ^ 1]: 7 left = mid + 1 8 else: 9 right = mid 10 return nums[left]
