Single Element in a Sorted Array

What does it solve?

In a sorted array, every element appears exactly twice, except one which appears only once. Find that single element in O(log n) — without scanning the whole array.

Before the single element, pairs line up at even indices (0-1, 2-3, ...). After it, every pair shifts by one, landing on odd indices instead. That shift is exactly what binary search latches onto.

The core idea

// force mid to an even index:
mid = (lo + hi) / 2
if mid is odd: mid--
if a[mid] == a[mid+1]:
  // pair intact — single is further right
  lo = mid + 2
else:
  // pair broken — single is here or left
  hi = mid

Complexity

Time complexity

O(log n)

Binary search on index parity — the window roughly halves every comparison.

Space complexity

O(1)

Just two pointers, lo and hi — no hash sets or extra arrays needed.

Examples & edge cases

Live animation

mid mid+1 pair matches pair broken the single element

Step — of —

Window [lo..hi]

—

mid (forced even)

—

Pair check

—

Step

—

Select an example and press Play to start.

✓ Complete

Speed Medium

Step-by-step table

Step	Window	mid	a[mid]	a[mid+1]	Decision

C++ implementation

single_element_sorted.cpp

#include <bits/stdc++.h>
using namespace std;

int singleNonDuplicate(vector<int>& nums) {
    int lo = 0, hi = nums.size() - 1;

    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (mid % 2 == 1) mid--;   // force mid to be even

        if (nums[mid] == nums[mid + 1]) {
            // pair is intact -> single element is further right
            lo = mid + 2;
        } else {
            // pair is broken -> single element is here or to the left
            hi = mid;
        }
    }
    return nums[lo]; // lo == hi, the single element
}

int main() {
    vector<int> nums = {1,1,2,3,3,4,4,8,8};
    cout << "Single element: " << singleNonDuplicate(nums) << "\n";
    return 0;
}

My Notes

📝 Notes ✅

▼

● Start typing to save... 0 chars