visual walkthrough
Single Element in a Sorted Array
Uses index parity to decide which side is broken.
The idea
Before the single number, every pair starts at an even position. The single number shifts everything after it by one, so pairs then start at odd positions.
Check an even position: if it matches its right neighbour, the single number is further right; if not, it's here or to the left.
Complexity
| approach | time | space |
|---|---|---|
| Check pair by pair | O(n) | O(1) |
| Binary search on pair alignment | O(log n) | O(1) |