题：给你一个仅由整数组成的有序数组，其中每个元素都会出现两次，唯有一个数只会出现一次。
请你找出并返回只出现一次的那个数。
你设计的解决方案必须满足 O(log n) 时间复杂度和 O(1) 空间复杂度。
示例：
输入: nums = [1,1,2,3,3,4,4,8,8]输出: 2
解：看到题目 中O(log n) 时间复杂度，容易想到二分查找。难点是这题中不是查找某一个值，而是查找一个单独的数。条件 nums[mid] ?? target 要如何改变？
单独元素前面有n对元素，即2n个元素，所以单独元素的下标一定是偶数。对偶数下标二分搜索。
若它与num[mid+1]是一对，则说明前面的都是成对的，low= mid+2;否则说明前面有单独的，high = mid。
class Solution: def singleNonDuplicate(self, nums: List[int]) -> int: low, high = 0, len(nums) - 1 while low < high: mid = (low + high) // 2 mid -= mid & 1 #mid -= mid & 1 作用是让mid取偶数。&是按位与，奇数&1 = 1,偶数&1 =0。 if nums[mid] == nums[mid + 1]: low = mid + 2 else: high = mid return nums[low]
如果 while循环用 <= 条件，需要high 初始化为len(nums)-2，否则会数组越界。 搜索空间为[0,len(nums)-2]，实际上mid最大取值len(nums)-2在区间内，所以有不会遗漏。
class Solution: def singleNonDuplicate(self, nums: List[int]) -> int: low, high = 0, len(nums) - 2 while low <= high: mid = (low + high) // 2 mid -= mid & 1 if nums[mid] == nums[mid + 1]: low = mid + 2 else: high = mid-2 return nums[low]
