Problem Statement
Single Element in Sorted Array
You are given a sorted list of numbers. Every number shows up exactly twice, except for one lonely number that shows up only once. Your job is to find that lonely number. The catch is speed: you must do it in O(log n) time, which means you cannot just walk through the whole list. O(log n) means the work roughly doubles in size each time you cut it in half, so for a list of a million numbers you only need about twenty steps. The tool that does this is binary search: you keep cutting the list in half and throwing away the half that cannot contain the answer. Here is the trick that makes it work. Think of the numbers as glued-together pairs sitting side by side. Before the lonely number, each pair is perfectly lined up: the first copy sits at an even spot in the line (positions 0, 2, 4, and so on, counting from 0). The lonely number breaks that alignment. After it, every pair gets shoved one spot over, so the first copy now sits at an odd spot. So the rule is: look at an even position, peek at it and the number right after it. If they match, the pairs are still lined up here, so the lonely number is further to the right. If they do not match, the break has already happened, so the lonely number is at this spot or to the left.
Signals to notice
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).
Trace it on nums=[3,3,7,7,10,11,11]
init: left=0, right=6 mid=(0+6)//2=3 → odd → mid=2; nums[2]=7==nums[3]=7? yes → left=mid+2=4 mid=(4+6)//2=5 → odd → mid=4; nums[4]=10==nums[5]=11? no → right=mid=4 left==right==4 → loop ends return nums[4]=10
What must stay true
The single element shifts all subsequent pairs. Binary search identifies where the shift occurs.
Shape of the loop
left, right = 0, n-1
while left < right:
mid = (left + right) // 2
if mid is odd: mid -= 1 # normalize to even
if nums[mid] == nums[mid+1]: left = mid + 2 # pair intact → go right
else: right = mid # break is at mid or left
return nums[left]Pseudocode only — the full worked solution lives in the Solution tab.
Easy way to go wrong
Not normalizing mid to even — if mid is odd, check mid-1. If even, check mid+1.