Single Element in a Sorted Array
Every element in a sorted array appears exactly twice, except one element that appears once. Find it in O(log n) time and O(1) space.
Intuition
Before the single element, pairs start at even indexes (0-1, 2-3, …). After it, that alignment breaks. Binary search for the first place the pairing is broken — that's where the loner hides.
Binary search on parity, not value. Before the single element, every pair starts at an even index; after it, that alignment breaks. Normalising mid to even and checking whether it pairs with mid + 1 tells you which side the anomaly lies on. Any problem where a property holds up to a point and then flips is binary-searchable.
Approach
The O(n) scan misses the point
XOR-ing everything, or scanning in steps of two, finds the answer — but the problem demands O(log n), which is a loud hint that the sorted structure carries information. What changes at the single element? The pair alignment.
Pair parity is the search signal
Left of the single element, every pair occupies indexes (even, even+1). At an even mid, if nums[mid] == nums[mid+1] the pairing is still intact — the loner must be right of the pair, so lo = mid + 2. If it differs, the break has already happened — the loner is at mid or left, so hi = mid. Force mid even first (mid -= 1 when odd) so the test is always well-formed.
Converge to the break point
The invariant 'loner is inside [lo, hi]' holds every round and the range halves each time, so when lo == hi it points exactly at the single element. No verification pass needed — return nums[lo].
Solution & live demo
Common pitfalls
Scanning linearly or XOR-ing everything
result = 0 for n in nums: result ^= n return result
while lo < hi:
mid = (lo + hi) // 2
if mid % 2 == 1: mid -= 1XOR gives the right answer but is O(n), and the problem explicitly asks for O(log n). The sortedness is the extra structure that makes a logarithmic solution possible.
Not normalising mid to an even index
if nums[mid] == nums[mid + 1]:
lo = mid + 2if mid % 2 == 1: mid -= 1
if nums[mid] == nums[mid + 1]:
lo = mid + 2The pairing argument only holds when comparing a pair's first element with its second. An odd mid compares across a pair boundary, so the parity test is meaningless and the search converges on the wrong half.
Using lo <= hi with hi = mid - 1
while lo <= hi:
...
else: hi = mid - 1while lo < hi:
...
else: hi = midmid itself may be the single element, so excluding it can step over the answer. Converging with lo < hi and keeping mid in range leaves lo sitting on it.
Edge cases
The very first pair test fails (nums[0] != nums[1]), so hi collapses to 0 immediately.
Every pair test passes; lo marches in steps of 2 to the final index.
Loop never runs (lo == hi already) — return the only element.