有序数组中的单一元素

这个题解使用了二分查找的思路。因为数组是有序的，且除了一个元素只出现一次外其他元素都出现两次，所以可以利用元素的下标的奇偶性来缩小查找范围。如果 mid 是偶数下标，则比较 nums[mid] 和 nums[mid+1]，如果两者相等，说明单一元素在 mid 之后，否则在 mid 及之前。如果 mid 是奇数下标，则比较 nums[mid] 和 nums[mid-1]，如果两者相等，说明单一元素在 mid 之后，否则在 mid 及之前。最终 begin 和 end 会指向同一位置，即为单一元素的下标。

时间复杂度: O(logn)

空间复杂度: O(1)

class Solution:
    def singleNonDuplicate(self, nums: List[int]) -> int:
        n = len(nums)
        begin,end = 0,n-1
        while begin<end:
            mid = (begin+end)//2
            if mid%2==0:
                if nums[mid]==nums[mid+1]:
                    # 如果 mid 是偶数下标且 nums[mid]==nums[mid+1]，说明单一元素在 mid 之后
                    begin = mid + 1 
                else:
                    # 否则单一元素在 mid 及之前
                    end = mid
            else:
                if nums[mid] == nums[mid-1]:
                    # 如果 mid 是奇数下标且 nums[mid]==nums[mid-1]，说明单一元素在 mid 之后
                    begin = mid + 1
                else:
                    # 否则单一元素在 mid 及之前
                    end = mid
        # 最终 begin 和 end 会指向同一位置，即为单一元素的下标
        return nums[end]