Single Element in a Sorted Array — Binary Search on Parity

What does it solve?

Every element in a sorted array appears exactly twice, except one. Find that single element in O(log N) (a linear XOR scan is O(N) but ignores the sorted structure).

Key insight: pairs are aligned (even, odd). Before the single element, the first of each pair sits at an even index; after it, that alignment breaks. Force mid to be even; if a[mid] == a[mid+1] the loner is to the right, else it's at or to the left. Binary search the break → O(log N).

The core idea

lo=0, hi=n-1
while lo < hi:
  mid=(lo+hi)/2
  if mid odd: mid-- # align to even
  if a[mid]==a[mid+1]: lo=mid+2 # pair intact → right
  else: hi=mid # break here or left
return a[lo]

Complexity

Time complexity

O(log N)

Binary search halves the pair-space each step. Beats the O(N) XOR-everything approach by using the sorted order.

Space complexity

O(1)

Two pointers, no extra structures.

Examples & edge cases

Live animation — binary search on pair alignment

lo mid (even) mid+1 partner hi single element

Sorted array

Current step detail

lo = — mid = — hi = — single = —

Step — of —

a[mid]

—

even index

a[mid+1]

—

partner

pair intact?

—

equal or not

single

—

the loner

Select an example and press Play to start.

✓ Done

SpeedMedium

Step-by-step table

Step	lo	mid	hi	a[mid],a[mid+1]	pair?	action

C++ implementation

single_element.cpp

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

// The one element appearing once in an otherwise-paired sorted array
int singleNonDuplicate(vector<int>& a) {
    int lo = 0, hi = (int)a.size() - 1;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (mid % 2 == 1) mid--;      // align mid to the even index of a pair
        if (a[mid] == a[mid + 1])
            lo = mid + 2;           // pair intact → single is to the right
        else
            hi = mid;               // break here → single is at mid or left
    }
    return a[lo];
}

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

My Notes

📝Notes✅

▼

●Start typing to save...0 chars

Practice this problem