Single Element in a Sorted Array: Binary Search on Pairs

LeetCode's Single Element in a Sorted Array is problem 540, and it is one of the most elegant binary search problems you will encounter. Every element in the array appears exactly twice, except for one. The array is sorted. Find the single element in O(log n) time and O(1) space. The constraint on time complexity rules out XOR and linear scans, pushing you toward binary search with a clever pairing observation.

The problem

You are given a sorted array where every element appears exactly twice except for one element that appears once. Find and return the single element.

Input:  [1, 1, 2, 3, 3, 4, 4, 8, 8]
Output: 2

The array has 9 elements. Every number shows up in a pair except for 2, which appears only once. Because the array is sorted, equal pairs are always adjacent.

The key insight: pair alignment

Here is the observation that makes this problem click. In a sorted array where everything is paired, pairs naturally align to even-odd index positions. The first pair occupies indices 0 and 1, the second pair occupies indices 2 and 3, and so on.

But the single element breaks this alignment. Before the single element, pairs start at even indices (0, 2, 4...). After the single element, pairs start at odd indices (because everything shifted by one position).

So if you land on an even index mid and check whether nums[mid] == nums[mid + 1], you can tell which side you are on:

• If the pair is intact at the even index, the single element is to the right. The alignment has not been disrupted yet.
• If the pair is broken, the single element is at mid or to the left.

For an odd index mid, the logic flips. The pair partner should be at mid - 1:

• If nums[mid] == nums[mid - 1], the pair is intact and the single element is to the right.
• Otherwise, the single element is at mid or to the left.

This gives you a binary search decision at every step: check whether the pair at mid is intact, and use that to determine which half contains the single element.

The code

Here is the clean Python solution for LeetCode 540:

def single_non_duplicate(nums):
    lo, hi = 0, len(nums) - 1

    while lo < hi:
        mid = lo + (hi - lo) // 2

        if mid % 2 == 1:
            mid -= 1

        if nums[mid] == nums[mid + 1]:
            lo = mid + 2
        else:
            hi = mid

    return nums[lo]

Let's break this down.

while lo < hi: We narrow the search space until one element remains. When lo == hi, that index holds the single element.

if mid % 2 == 1: mid -= 1: This forces mid to always be even. By doing this, we only need one comparison rule: check nums[mid] against nums[mid + 1]. No separate logic for odd indices.

if nums[mid] == nums[mid + 1]: The pair at this even index is intact. The single element has not disrupted things yet, so it must be further to the right. We skip past both elements of the pair with lo = mid + 2.

else: hi = mid: The pair is broken. The single element is at mid or somewhere to the left. We cannot skip mid because it might be the answer, so hi = mid.

Step-by-step walkthrough

Let's trace through nums = [1, 1, 2, 3, 3, 4, 4, 8, 8]. The single element is 2 at index 2.

Three real comparisons, then convergence. Out of 9 elements, we found the single element in O(log n) time. The pair-checking logic cuts the search space in half at every step.

Complexity analysis

Time: O(log n). Each step halves the search space. The loop runs at most log2(n) times.

Space: O(1). Three variables: lo, hi, mid. No extra data structures.

The XOR approach is simpler to code (just XOR everything together), but it does not exploit the sorted property and runs in O(n). The binary search solution is optimal for the given constraints.

The building blocks

This problem is built on one core building block: binary-search-template.

The skeleton is the standard binary search: maintain [lo, hi], compute mid, eliminate half the range. The twist is the decision logic. Instead of comparing nums[mid] to a target, you check whether the pair at mid is intact to determine which half contains the disruption.

# Standard binary search (find target):
while lo <= hi:
    mid = lo + (hi - lo) // 2
    if nums[mid] == target:
        return mid
    elif nums[mid] < target:
        lo = mid + 1
    else:
        hi = mid - 1

# Single element in sorted array:
while lo < hi:
    mid = lo + (hi - lo) // 2
    if mid % 2 == 1:
        mid -= 1
    if nums[mid] == nums[mid + 1]:
        lo = mid + 2
    else:
        hi = mid

Same structure, different comparison. The "force mid to even" trick simplifies the logic so you do not need separate branches for odd and even indices.

This "binary search on a structural property" pattern shows up in several related problems:

• Find Peak Element (LeetCode 162): binary search where you compare mid to its neighbor to find a slope change
• Find Minimum in Rotated Sorted Array (LeetCode 153): compare mid to the boundary to locate the rotation pivot
• Search in Rotated Sorted Array (LeetCode 33): determine which half is sorted to decide where the target lives

Edge cases

Before submitting, verify your solution handles:

• Single element array: nums = [1]. lo == hi from the start, so the loop never runs. Return nums[0] = 1.
• Single at the beginning: nums = [2, 3, 3]. mid = 0 (even), nums[0] != nums[1], so hi = 0. Return nums[0] = 2.
• Single at the end: nums = [1, 1, 2]. mid = 0 (even), nums[0] == nums[1], so lo = 2. Now lo == hi, return nums[2] = 2.
• Large array: The algorithm handles arrays up to the constraint limit because it only does O(log n) comparisons.
• All same except one: nums = [5, 5, 5, 5, 3, 5, 5] is not valid input because the array must be sorted. The sorted constraint guarantees that equal pairs are always adjacent.

The binary search solution handles all valid inputs without special cases.

From understanding to recall

The logic is elegant: force mid to be even, check if the pair is intact, go right if it is, go left if it is not. You understand it now.

But in an interview three weeks from now, the details will be fuzzy. Was it lo = mid + 1 or lo = mid + 2? Do you force mid to be even or odd? Do you compare to mid + 1 or mid - 1? These are small decisions, but getting any one of them wrong means a broken solution.

Spaced repetition is perfect for this. You write the solution from scratch today, again tomorrow, then in four days. By the third repetition, the "force mid even, skip two on match" pattern is locked in. You are not re-deriving it under pressure. You just write it.

LeetCode 540 is an ideal SRS candidate: the code is short (eight lines), the idea is clean, but the index arithmetic is easy to mess up. Drill it a few times and it becomes automatic.

Related posts

• Binary Search (LeetCode 704): The Foundation - Master the standard binary search template first, then this pair-checking variant becomes a small modification
• Find Minimum in Rotated Sorted Array (LeetCode 153): Binary Search on the Pivot - Another problem where binary search works by checking a structural property rather than comparing to a target
• Find Peak Element (LeetCode 162): Binary Search on Slope - Binary search using neighbor comparisons to find where a property changes

CodeBricks breaks the binary search pattern into its reusable pieces and drills them individually. You type the pair-checking logic from scratch each time, building the muscle memory so that when you see Single Element in a Sorted Array or any similar index-manipulation problem in an interview, the code flows without hesitation.