← DSA Atlas
Dedicated problem page · #540

Single Element in a Sorted Array

MediumBinary SearchParity-anchored binary searchBinary search on a sorted array
Solve on LeetCode ↗
540
MediumBinary SearchBinary search on a sorted arrayParity-anchored binary search

Single Element in a Sorted Array

You are given a sorted array of integers in which every element appears exactly twice except for one element that appears exactly once. Return that single element. Your solution must run in O(log n) time and O(1) space.

Open official problem prompt ↗
In plain English

Locate the one unpaired value in a sorted array without scanning every element.

Picture it like this

Imagine dancers lined up in couples. Up to some point every couple stands shoulder to shoulder; the moment one person is missing a partner, everyone after shifts by one spot. You binary-search for exactly where the neat pairing first fails.

Example
Input
nums = [1,1,2,3,3,4,4,8,8]
Output
2
Why
Every value forms a pair except 2, which appears only once.
Constraints
1 <= nums.length <= 10^50 <= nums[i] <= 10^5nums is sorted in non-decreasing orderExactly one element appears once; all others appear exactly twice
Pattern lesson

See the pattern, then code

Parity-anchored binary search
Recognition clue

A sorted array plus an explicit O(log n) requirement rules out a linear XOR scan and points at binary search; the twist is deciding what to compare mid against.

↗
Binary Search

Sorted data or a monotonic true/false condition over a possible answer.. Before the single element, each pair starts at an even index (pair at 0-1, 2-3, ...). After it, that alignment breaks and pairs start at odd indices. Force mid to an even index and check nums[mid] == nums[mid+1]: if they still match, the anomaly is to the right; otherwise it is at or to the left of mid.

New words, made simpleKnow these before the algorithm
Invariant
A condition kept true across every loop iteration; here, the single element always lies within [lo, hi].
Parity
Whether an index is even or odd; used to align mid to the start of a pair.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
XOR all elements

Correct and elegant but linear, so it violates the required O(log n) bound.

XOR every value; paired values cancel and the lone one remains.

Time O(n)Space O(1)
Best choiceBinary search on pair parity

Meets the logarithmic requirement and exploits the sorted structure directly.

Anchor mid to an even index and test nums[mid]==nums[mid+1] to decide which half still holds the anomaly.

Time O(log n)Space O(1)
The rule we keep true

Invariant

The single (unpaired) element always lies within the closed range [lo, hi].

Why this is correct

Reasoning

Left of the single element, the first occurrence of every pair sits at an even index, so an even mid matching its right neighbor proves the anomaly is strictly to the right. Once the single element is passed, that even-index property is destroyed, so a mismatch means the anomaly is at or before mid. Each step halves the search window while preserving the invariant, so it converges on the lone element.

The algorithm in three movesSay these aloud before coding
1Set lo=0 and hi=len(nums)-1

lo=0 hi=8 mid=4 nums[4]=3==nums[5]? no -> hi=4

2Take mid and round it down to an even index

lo=0 hi=4 mid=2 nums[2]=2==nums[3]? no -> hi=2

3If nums[mid] == nums[mid+1] the single element is right of mid, so lo = mid+2

lo=0 hi=2 mid=0 nums[0]=1==nums[1]? yes -> lo=2 == hi -> return 2

4Otherwise it is at or left of mid, so hi = mid

5When lo == hi, nums[lo] is the answer

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
10
11
22
33
34
45
46
87
88
1 · Readnums=[1,1,2,3,3,4,4,8,8]
2 · AskIs the single element in [0,8]?
3 · Update statelo=0, hi=8
4 · Resultmid=4 (even); nums[4]=3, nums[5]=4 differ -> hi=4
Key takeaway

The single element 2 breaks the even-index pairing that holds everywhere to its left.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 3Initialize the search window

    lo and hi bracket the entire array; the answer is guaranteed inside.

  2. 2
    Lines 5-7Anchor mid to an even index

    Rounding an odd mid down to even ensures we always compare against the intended start of a pair.

  3. 3
    Lines 8-11Decide which half survives

    A matching pair at an even mid means everything up to mid+1 is clean, so the anomaly is at mid+2 or later; otherwise it is at or before mid.

  4. 4
    Lines 12Return the survivor

    When the window collapses to one index, that element is the unpaired one.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • Array of length 1 (the sole element is the answer)
  • Single element at the very first index
  • Single element at the very last index
  • Single element exactly in the middle
!

Common beginner mistakes

  • Forgetting to force mid to an even index, which breaks the parity argument
  • Using lo <= hi with hi = mid, causing an infinite loop
  • Accessing nums[mid+1] without guaranteeing mid is even and in bounds
  • Reaching for XOR out of habit and missing the O(log n) requirement
Check your understanding

Why must mid be rounded to an even index rather than left arbitrary?

More in Binary Search

#33Search in Rotated Sorted ArrayBinary search on a rotated array#153Find Minimum in Rotated Sorted ArrayBinary search for the rotation point#875Koko Eating BananasBinary search on the answer#4Median of Two Sorted ArraysBinary search on the partition#34Find First and Last Position of ElementLower-bound binary search on both ends#35Search Insert PositionLower-bound binary search