Data Structures and Algorithms (DSA)  

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

  1. Set low = 0, high = n - 1

  2. Find mid

  3. Make mid even (if odd, subtract 1)

  4. If arr[mid] == arr[mid + 1], move right

  5. Else, move left

  6. Continue until low == high

That index contains the single element.

Dry Run Example

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

lowhighmidcheckmove
0622 != 3left
0201 == 1right
22-stopanswer

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.

Membership not found