Single Element in Sorted Array
mediumTime: O(log n)Space: O(1)
Recognize the pattern
single non-duplicate in sorted paired arrayO(log n)pairing pattern disrupted
Brute force idea
XOR all — O(n). Doesn't use sorted structure.
Better approach
Binary search: before the single element, pairs start at even indices. After, at odd. Check mid's pair to determine which side. O(log n).
Key invariant
The single element shifts all subsequent pairs. Binary search identifies where the shift occurs.
Watch out for
Not normalizing mid to even — if mid is odd, check mid-1. If even, check mid+1.