Single Element in Sorted Array
mediumTime: O(log n)Space: O(1)
Signals to notice
single non-duplicate in sorted paired arrayO(log n)pairing pattern disrupted
Brute force first
XOR all — O(n). Doesn't use sorted structure.
The key insight
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).
What must stay true
The single element shifts all subsequent pairs. Binary search identifies where the shift occurs.
Easy way to go wrong
Not normalizing mid to even — if mid is odd, check mid-1. If even, check mid+1.