Single Element in a Sorted Array Using Binary Search

Introduction

The Single Element in a Sorted Array problem is a popular DSA interview question that tests your understanding of binary search.

In simple terms, this problem asks you to find the only number that appears once, while all other numbers appear exactly twice.

This article explains the solution using Binary Search, written in simple, human-friendly language, with real-world meaning and clear step-by-step logic.

Real-World Meaning of Single Element

Imagine a sock drawer:

Every sock has a pair
Except for one sock that has no pair

If the socks are neatly arranged, you can find the single sock faster by checking patterns rather than checking each sock one by one.

This is exactly how this problem works.

Problem Statement

You are given a sorted array where:

Every element appears exactly twice
Except one element,for which appears only once

Your task is to find that single element.

Example

Array: [1, 1, 2, 3, 3, 4, 4]
Output: 2

Before vs After Understanding

Linear Scan (Before)

Check elements one by one
Compare neighbors
Works, but slow

Binary Search (After)

Use index patterns
Skip half of the array
Much faster

Key Observation (Very Important)

In a correctly paired array:

Pairs start at even index
First element of each pair is at even index
Second element is at odd index

Once the single element appears, this pattern breaks.

Why Binary Search Works Here

Because the array is:

Sorted
Mostly following a strict index pattern

Binary search helps us quickly find where the pattern breaks.

What Interviewers Are Actually Testing

Interviewers want to see:

Can you observe patterns in data?
Can you modify binary search logic?
Can you solve without extra space?

This problem tests logical thinking, not memorization.

Key Idea (Very Simple)

Check the middle index
Make sure mid is even
If pair is correct, move right
If pair is broken, move left

Step-by-Step Logic

Set low = 0, high = n - 1
Find mid
Make mid even (if odd, subtract 1)
If arr[mid] == arr[mid + 1], move right
Else, move left
Continue until low == high

That index contains the single element.

Dry Run Example

Array: [1, 1, 2, 3, 3, 4, 4]

low	high	mid	check	move
0	6	2	2 != 3	left
0	2	0	1 == 1	right
2	2	-	stop	answer

Answer = 2

One-Line Logic Before Code

Use index pairing pattern and binary search to find where it breaks.

Code Implementation (C++)

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

    while (low < high) {
        int mid = low + (high - low) / 2;
        if (mid % 2 == 1)
            mid--;

        if (nums[mid] == nums[mid + 1])
            low = mid + 2;
        else
            high = mid;
    }
    return nums[low];
}

Common Beginner Mistakes

Forgetting to adjust mid to even index
Using linear scan in interviews
Ignoring sorted property

Time and Space Complexity

Time Complexity: O(log n)
Space Complexity: O(1)

Easy Summary (Explain Like I’m 10)

If every number has a pair except one, the pairs follow a pattern. When that pattern breaks, you’ve found the odd one out. Binary search helps you find that break quickly without checking everything.

Summary

Finding the single element in a sorted array using binary search is an elegant problem that relies on observing index patterns rather than scanning values. By ensuring pairs start at even indexes and narrowing the search space where this pattern breaks, you can solve the problem efficiently in logarithmic time. This question is commonly asked in interviews and strengthens your understanding of advanced binary search techniques.