One question per day 540 A single element in an ordered array

topic ： Give you an ordered array of integers only , Each of these elements will appear twice , Only one number will appear once .

Please find and return the number that only appears once .

The solution you design must meet O(log n) Time complexity and O(1) Spatial complexity .

Example ：

 Input : nums = [1,1,2,3,3,4,4,8,8]
 Output : 2

Explain ： See the title in O(log n) Time complexity , It's easy to think of binary search . The difficulty is that this problem is not to find a certain value , Instead, look for a single number . Conditions nums[mid] ?? target How to change ？

Individual elements are preceded by n The element , namely 2n Elements , So the subscripts of individual elements must be even . Binary search for even subscripts .

If it is related to num[mid+1] It's a pair. , It means that the front ones are all in pairs ,low= mid+2; Otherwise, there is a separate ,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  The function is to make mid Take even number .& It's bitwise and , Odd number &1 = 1, even numbers &1 =0.

            if nums[mid] == nums[mid + 1]:
                low = mid + 2
            else:
                high = mid
        return nums[low]

If while Recycle <= Conditions , need high Initialize to len(nums)-2, Otherwise, the array will be out of bounds . The search space is [0,len(nums)-2], actually mid Maximum value len(nums)-2 In the interval , So there will be no omission .

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]