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.
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
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.