Binary search normally needs a target value to chase. This problem has no target, and yet the sorted array still supports O(log n) search — because a sorted list of pairs carries a hidden invariant that answers the “which half” question for free. Write the indices out under the values: every element appears exactly twice and the array is sorted, so duplicates come as adjacent pairs. Before the single element, each pair occupies two consecutive slots starting at an even index — (0, 1), (2, 3), and so on. After the single element, the same pairs occupy slots starting at an odd index. So the single element must sit at an even index, and every even index answers one yes/no question about it: does my right neighbor carry the same value? Yes means that slot is an intact pre-single pair, so the single is still ahead; no means the single is at or left of me. One yes/no answer at the middle of the surviving range is enough to discard half of it — binary search with no target, built on a parity invariant.
Brute Force: Linear Scan Over the Pairs
Time O(n)Space O(1)The sorted array keeps duplicates adjacent, so scan the pairs two cells at a time, stepping through the even indices. Before the single element every (even, odd) slot holds an equal pair; the first slot whose two cells differ is leaking the single as its left element — return that left element. If no slot ever lies, every pair is intact and the single is the very last element.
class Solution: def singleNonDuplicate(self, nums: list[int]) -> int: # Before the single, every pair owns an (even, odd) slot. # The first broken slot leaks the single on its left. for i in range(0, len(nums) - 1, 2): if nums[i] != nums[i + 1]: return nums[i] return nums[-1]Why it is linear: the single can hide at the very end, in which case every pair gets inspected — about n / 2 checks — so the scan takes O(n) time, and it uses no extra memory beyond the loop variable. A popular O(n) shortcut XORs the whole array instead (x ^ x = 0 erases every pair, leaving only the lone value) — elegant, but it ignores sortedness entirely, so it says nothing about how to reach the O(log n) the problem demands.
Binary Search: Halve the Range by Parity
OptimalTime O(log n)Space O(1)Turn the invariant into a test. The single can only sit at an even index, so normalize every midpoint to an even index — step back one when the midpoint lands odd — and test that even index against its right neighbor. The test has exactly two outcomes. Equal means the slot is an intact pre-single pair, so the single lies strictly past it: both cells are consumed and lo jumps by two. Different means the single is at or left of the midpoint: hi slides in, keeping the failing index itself as a candidate. The range never needs a recalc of parity because both bounds stay even, so no candidate is ever skipped.
class Solution: def singleNonDuplicate(self, nums: list[int]) -> int: lo, hi = 0, len(nums) - 1 while lo < hi: mid = (lo + hi) // 2 # The single can only sit at an even index, so normalize mid # to even: the test is always even index vs right neighbor. if mid % 2 == 1: mid -= 1 if nums[mid] == nums[mid + 1]: lo = mid + 2 # intact (even, odd) pair: single is past it else: hi = mid # broken even slot: single is at or left return nums[lo]Trace example 1 end to end — every comparison of the halving on nums = [1,1,2,3,3,4,4,8,8], from the parity invariant to the collapse onto index 2:
the test is always the same shape: an even index against its right neighbor — one comparison halves the range
Duplicates sit in equal adjacent pairs around one lone value. Before the single, a pair owns the (even, odd) slots; after it, the (odd, even) slots. An even index whose right neighbor differs signals the single lies at or left.
Trace example 2 takes the other branch first — an intact pair moves lo, then a mismatch pulls hi back, arriving at index 4 in two comparisons:
the test is always the same shape: an even index against its right neighbor — one comparison halves the range
Second example: nums = [3,3,7,7,10,11,11], where the single 10 sits at index 4. This trace hits the two branches in the opposite order: an intact pair moves lo first, then a mismatch pulls hi back.
Why it is O(log n): every round halves the surviving range, so the loop runs log₂ n times, each round doing constant work — one pair comparison plus two index updates; space stays O(1) with just the two pointers. The structure keeps itself honest: n is always odd (pairs plus the single), the bounds stay even, and mid + 1 never escapes the array, so the neighbor test is always safe. The brute force re-checks every pair when the single sits late; this search checks only log₂ n of them.