Single Element in a Sorted Array

Intuition

Solution

class Solution:
    def singleNonDuplicate(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return nums[0]
        if nums[0] != nums[1]:
            return nums[0]
        lo = 0
        hi = (len(nums) - 1) // 2
        while hi - lo > 1:
            mid = (lo + hi) // 2
            if nums[2 * mid] == nums[2 * mid + 1]:
                lo = mid
            else:
                hi = mid

        return nums[2 * hi]