The problem
In a sorted list, every value appears twice except one. Find the single one in O(log n).
Input: [1, 1, 2, 3, 3, 4, 4, 8, 8] Output: 2
Picture it
Picture socks hanging in pairs on a washing line, with one lone sock. Before the lone sock, each pair starts at an even position; after it, pairs start at odd positions. Checking the middle pair tells us which side the lone sock is on.
Short version: the full lesson (brute force, complexity, edge cases and a quiz) is still being written. The animation is complete.
The key idea
Binary search on pair alignment (even index pairs with index + 1). O(log n).
Python solution
def single(a):
lo, hi = 0, len(a) - 1
while lo < hi:
mid = (lo + hi) // 2
if mid % 2:
mid -= 1 # pairs start at even spots
if a[mid] == a[mid + 1]:
lo = mid + 2 # pattern intact: lone sock is right
else:
hi = mid # pattern broken: lone sock is here or left
return a[lo]In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.