LeetCode 540 · Binary search

Single Element in a Sorted Array, explained with a picture

The lone sock on a line of pairs.

Binary search
▶ Watch it step by step

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.