Single Element In A Sorted Array

Single Element in a Sorted Array: Finding the Unique Value with Binary Search

When a sorted array contains pairs of identical numbers and exactly one element appears only once, locating that lone value efficiently becomes a classic interview and algorithm‑design challenge. The problem is often phrased as “find the single element in a sorted array” because the array’s ordering lets us discard half of the search space at each step, achieving logarithmic time complexity. Below is a thorough walk‑through of the concept, the reasoning behind the optimal solution, practical implementation details, and answers to common questions Surprisingly effective..

Introduction

The single element in a sorted array problem assumes the following constraints:

• The array is sorted in non‑decreasing order.
• Every element appears exactly twice, except for one element that appears once.
• The array length is therefore odd ( 2 × k + 1 ).

Because of the pairing property, the indices of duplicate values follow a predictable pattern: the first occurrence of a pair sits at an even index, and the second occurrence sits at the next odd index—as long as we are still before the single element. After the unique value, this pattern flips: pairs start at odd indices and end at even indices. Exploiting this shift lets us apply binary search to locate the disruption in O(log n) time.

Problem Statement

Input: A sorted integer array nums of length n where n is odd, and every element appears exactly twice except one element that appears once.
Output: The value of the element that appears only once.

Example

Input:  [1,1,2,3,3,4,4,8,8]
Output: 2

The array is sorted, pairs are (1,1), (3,3), (4,4), (8,8), and the lone element is 2.

Approach Overview

A naïve solution would scan the array linearly, checking each element against its neighbor, yielding O(n) time. The sorted nature, however, invites a divide‑and‑conquer strategy:

1. Identify the middle index mid.
2. Determine whether the pair pattern holds at mid.
3. If the pattern holds, the single element must be to the right; otherwise, it is to the left (including mid).
4. Repeat until the search space collapses to one index.

The key insight is the parity check:
*If mid is even, the first copy of a pair should be at mid and the second at mid+1.
Day to day, if mid is odd, the second copy should be at mid and the first at mid‑1. When the expected neighbor does not match nums[mid], the disruption lies at or before mid; otherwise, it lies after mid Most people skip this — try not to. Practical, not theoretical..

Binary Search Solution – Step‑by‑Step

Below is a detailed algorithmic breakdown.

1. Initialise Pointers

left  = 0
right = n - 1          // inclusive bound

2. While left < right

mid = left + (right - left) // 2

3. Make mid even (optional but simplifies logic)

If mid is odd, decrement it by 1 so that we always compare an even index with its next odd index. This guarantees we are looking at the first element of a potential pair.

if mid % 2 == 1:
    mid -= 1

4. Compare the pair

• If nums[mid] == nums[mid + 1] → the pair is intact, meaning the single element is after this pair.
  → Set left = mid + 2 The details matter here..

• Else → the pair is broken; the single element is at mid or before it.
  → Set right = mid That alone is useful..

5. Termination

When left == right, the search space has narrowed to a single index, which holds the answer. Return nums[left].

Correctness Proof Sketch

We prove by invariant that the algorithm never discards the single element And that's really what it comes down to..

Invariant: At the start of each iteration, the single element lies within the inclusive interval [left, right].

Base: Initially [0, n‑1] obviously contains the answer Not complicated — just consistent..

Maintenance:

• If nums[mid] == nums[mid+1] (after forcing mid even), then indices mid and mid+1 form a correct pair before the single element. Hence the answer cannot be in [left, mid+1]; we safely set left = mid+2.
• If they differ, the disruption occurs at or before mid. Since mid is the first index of a potentially broken pair, the answer lies in [left, mid]; we set right = mid.

Termination: When left == right, the interval size is one, and by the invariant it must contain the single element. Thus nums[left] is correct.

Complexity Analysis

Reference Implementations

Python 3

def single_non_duplicate(nums):
    left, right = 0, len(nums) - 1
    while left < right:
        mid = left + (right - left) // 2
        # ensure mid is even
        if mid % 2 == 1:
            mid -= 1
        if nums[mid] == nums[mid + 1]:
            # pair is fine, move right
            left = mid + 2
        else:
            # pair broken, answer is at mid or left side
            right = mid
    return nums[left]

# Example
print(single_non_duplicate([1,1,2,3,3,4,4,8,8]))  # → 2

Java

public class SingleElementFinder {
    public static int singleNonDuplicate(int[] nums) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (mid % 2 == 1) mid--;   // make mid even
            if (nums[mid] == nums[mid + 1]) {
                left = mid + 2;
            } else {
                right = mid;
            }
        }
        return nums[left];
    }

    public static void main(String[] args)