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?