Single Element in a Sorted Array

Problem Statement

Given a sorted array where:

• Every element appears exactly twice.
• Only one element appears once.

Find the single element in O(log N) time and O(1) space.

Brute Force Intuition

In an interview, you can explain it like this:

Since every element appears twice except one, we can iterate through the array and count frequencies. The element with frequency 1 is our answer. This works but doesn't utilize the sorted nature of the array.

Complexity

• Time Complexity: O(N)
• Space Complexity: O(1)

Brute Force Code

class Solution {

    public int singleNonDuplicate(int[] nums) {

        for (int i = 0; i < nums.length - 1; i += 2) {

            if (nums[i] != nums[i + 1]) {
                return nums[i];
            }
        }

        return nums[nums.length - 1];
    }
}

Moving Towards the Optimal Approach

The important observation is:

Before the single element:

Index: 0 1 2 3 4 5
Array: 1 1 2 2 3 3

Pairs start at EVEN indices.

After the single element:

Index: 0 1 2 3 4 5 6
Array: 1 1 2 3 3 4 4

Pairs start at ODD indices.

The single element breaks the pairing pattern.

This allows us to use Binary Search.

Pattern Recognition

Whenever you see:

• Sorted Array
• Pair Pattern
• One Missing / One Unique Element

Think:

Binary Search on Index Pattern

Optimal Approach

Observation

If:

nums[mid] == nums[mid + 1]

then:

• If mid is even → single element lies on right.
• Otherwise → lies on left.

To simplify:

if(mid % 2 == 1)
    mid--;

Now every mid becomes even.

Optimal Java Solution

class Solution {

    public int singleNonDuplicate(int[] nums) {

        int low = 0;
        int high = nums.length - 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];
    }
}

Dry Run

Input

nums = [1,1,2,2,3,4,4]

Iteration 1

low = 0
high = 6

mid = 3
mid = 2 (make even)

nums[2] = 2
nums[3] = 2

Pair exists.

Move Right

low = 4

Iteration 2

low = 4
high = 6

mid = 5
mid = 4

nums[4] = 3
nums[5] = 4

Pair broken.

Move Left

high = 4

Result

low = high = 4

Answer = 3

Why This Works?

Before the single element:

Pair starts at Even Index

After the single element:

Pair starts at Odd Index

Binary Search helps identify where this pattern breaks.

Complexity Analysis

Interview One-Liner

In a sorted array, pairs start at even indices before the single element and at odd indices after it. Binary search on this pattern finds the answer in O(log N).

Pattern Learned

Sorted Array
+
Pair Structure
+
One Unique Element

=> Binary Search on Index Pattern