Single Element in a Sorted Array
Binary search on pair alignment
Scanning with XOR solves this in O(n), but the array is sorted, and sorting buys something stronger: position. Before the single element, each pair occupies an even index and the odd index after it. From the single element onward every pair is shifted by one, so pairs now START on odd indices. Force mid onto an even index and peek at its neighbour: if they match, the alignment is unbroken and the loner is further right; if they differ, the break has already happened and the loner is at mid or to its left. Half the array dies every comparison.
Details
Animated on: nums = [1,1,2,3,3,4,4,8,8] — every element appears exactly twice except one. Return that element in O(log n) time.
Problem:Single Element in a Sorted ArrayMedium
Binary search on pair alignment
step 1 / 8
Every value appears twice except one, so the pairs before the loner start at EVEN indices (0-1, 2-3, ...) and the pairs after it are shifted to start at ODD indices. That broken alignment is what binary search hunts for over 9 cells.
- lo=0· arr[0] = 1
- hi=8· arr[8] = 8
1FUNCTION singleNonDuplicate(nums)2 lo <- 03 hi <- LENGTH(nums) - 14 WHILE lo < hi5 mid <- (lo + hi) / 26 IF mid MOD 2 = 17 mid <- mid - 18 IF nums[mid] = nums[mid + 1]9 lo <- mid + 210 ELSE11 hi <- mid12 RETURN nums[lo]
← / → step · space play · Home restart
Every step in words
Show all 8 steps
- Every value appears twice except one, so the pairs before the loner start at EVEN indices (0-1, 2-3, ...) and the pairs after it are shifted to start at ODD indices. That broken alignment is what binary search hunts for over 9 cells.
- Midpoint of 0..8 is even index 4, so it already opens a pair — compare nums[4]=3 with its partner nums[5]=4.
- nums[4]=3 and nums[5]=4 differ, so the alignment is ALREADY broken by index 4 — the loner sits at 4 or earlier. Pull hi down to 4 and throw away everything to its right.
- Midpoint of 0..4 is even index 2, so it already opens a pair — compare nums[2]=2 with its partner nums[3]=3.
- nums[2]=2 and nums[3]=3 differ, so the alignment is ALREADY broken by index 2 — the loner sits at 2 or earlier. Pull hi down to 2 and throw away everything to its right.
- Midpoint of 0..2 landed on odd index 1, which is the SECOND half of a pair — step back to 0 so mid always opens a pair, then compare nums[0]=1 with its partner nums[1]=1.
- nums[0] and nums[1] are both 1, so pairing is still intact at index 0 — the loner cannot be at or before 1. Jump lo past this whole pair to 2.
- lo and hi met at index 2: it is the first even index whose partner does not match, so nums[2]=2 is the element that appears only once.
Now solve it yourself
Watching is the first half. The second is writing it without the animation.