The key signal is index parity. Before the single element, pairs are aligned as (even, odd): for example (0,1), (2,3), (4,5). After the single element, this alignment shifts by one, so pairs become (odd, even).

That gives us a boolean test to_the_left(idx): if it returns True, the single element is at idx or somewhere to its left. if it returns False, the single element is strictly to the right.

For an odd index idx, compare with the previous element: if nums[idx] != nums[idx - 1], the shift has already happened, so the single element is on the left. For an even index idx, compare with the next element: if nums[idx] != nums[idx + 1], normal pairing is broken here, so the single element is on the left.

The only boundary case is when idx is the last index. Then there is no idx + 1, and the answer must be at or to the left, so return True.

Implementation

def singleNonDuplicate(self, nums):
    def to_the_left(idx):
        if (idx == len(nums)-1):
            return True
        elif (idx % 2):   # odd
            return nums[idx] != nums[idx-1]
        else:             # even
            return nums[idx] != nums[idx+1]

    left, right, ans = 0, len(nums)-1, -1
    while left <= right:
        mid = (left + right) // 2
        if to_the_left(mid):
            ans = mid
            right = mid - 1
        else:
            left = mid + 1

    return nums[ans]