Binary Search (DSA) - Chapter 8: Single Element in Sorted Array

This chapter explores how to efficiently find the single non-duplicate element in an otherwise perfectly paired, sorted array. We will evolve from a naive linear scan to an optimal binary search approach running in $O(\log n)$ time, mastering advanced search-space reduction and edge-case management along the way.

1. Problem Statement & Overview

We are given a sorted array of integers where every single number appears exactly twice, except for one unique number which appears only once. Because the array is sorted, identical elements appear contiguously in adjacent pairs (couples).

Index:    0   1   2   3   4   5   6   7   8
Array:  [ 1,  1,  2,  2,  3,  5,  5,  6,  6 ]
                               ^
                          Single Element (3)

Key Guarantees

• A single element is always guaranteed to exist.
• All other numbers appear in pairs.
• The array is sorted, meaning duplicate elements sit side-by-side.

2. Naive Approach: Linear Scan ($O(n)$ Time)

The most intuitive brute-force strategy is to iterate through every element and check its left and right neighbors to determine if it belongs to a pair.

How the Naive Approach Works

1. If we are at index 0, we check only the right neighbor (index + 1).
2. If we are at index n - 1, we check only the left neighbor (index - 1).
3. For any middle index i, if arr[i] is not equal to arr[i - 1] and not equal to arr[i + 1], then arr[i] is our single element.

Naive Code Implementation

public int singleNonDuplicate(int[] arr) {
    int n = arr.length;
    
    // Exception case for single-element array
    if (n == 1) return arr[0];
    
    for (int i = 0; i < n; i++) {
        if (i == 0) {
            if (arr[i] != arr[i + 1]) return arr[i];
        } else if (i == n - 1) {
            if (arr[i] != arr[i - 1]) return arr[i];
        } else {
            if (arr[i] != arr[i + 1] && arr[i] != arr[i - 1]) {
                return arr[i];
            }
        }
    }
    return -1;
}

Complexity & Limitations

• Time Complexity: $O(n)$ because we scan every element in the worst case.
• Space Complexity: $O(1)$.
• Drawback: In an interview, an $O(n)$ solution will not impress. Since the array is sorted, we should immediately think of Binary Search to achieve $O(\log n)$ time.

3. Core Mental Model: The Index Pattern Observation

To apply Binary Search, we must be able to eliminate half of the search space at each step. To do this, we need to discover a structural property governed by the single element.

Let's examine the index pairings before and after the single element appears:

Index:    0    1    2    3    4    5    6    7    8
Array:  [ 1,   1,   2,   2,   3,   5,   5,   6,   6 ]
Pairs:   (even,odd) (even,odd)  SINGLE  (odd,even) (odd,even)

The Index Parity Rule

• Before the single element:
  • The first instance of a pair is always at an even index.
  • The second instance of a pair is always at an odd index.
  • Example: 1 is at (0, 1), 2 is at (2, 3).
• After the single element:
  • The pattern shifts! The first instance of a pair lands on an odd index, and the second instance lands on an even index.
  • Example: 5 is at (5, 6), 6 is at (7, 8).

Summary Rule for Binary Search Navigation

4. Engineering Clean Code: Eliminating Edge Cases

If we run binary search across the full array from 0 to n - 1, our mid-pointers will constantly risk checking out-of-bounds indices (mid - 1 when mid = 0, or mid + 1 when mid = n - 1). Writing guards for every check makes code unreadable and messy.

The Pro-Developer Strategy: Trim the Search Space First

Instead of cluttering our binary search loop with boundary checks, we can:

1. Handle arrays of size 1 instantly.
2. Check the boundary elements (0 and n - 1) manually upfront.
3. Run our binary search strictly within the inner range: low = 1 to high = n - 2.

5. Step-by-Step Flow Walkthrough

Let's trace arr = [1, 1, 2, 2, 3, 5, 5, 6, 6] ($n = 9$).

1. Manual Boundary Check:
   • Check index 0: arr[0] = 1, arr[1] = 1 (Equal, so not single).
   • Check index 8: arr[8] = 6, arr[7] = 6 (Equal, so not single).
2. Initialize Binary Search Range:
   • low = 1, high = 7.
3. Iteration 1:
   • mid = (1 + 7) / 2 = 4. arr[4] = 3.
   • Check if mid is the single element:
     • arr[4] (3) != arr[3] (2) AND arr[4] (3) != arr[5] (5). Both neighbors differ!
     • Result: 3 is our single element. Return 3.

6. Complete Production-Ready Code

Here is the clean, interview-optimized Java implementation implementing the strategies discussed above:

class Solution {
    public int singleNonDuplicate(int[] arr) {
        int n = arr.length;
        
        // Edge Case: If array size is 1
        if (n == 1) {
            return arr[0];
        }
        
        // Check the first element separately to avoid boundary issues
        if (arr[0] != arr[1]) {
            return arr[0];
        }
        
        // Check the last element separately to avoid boundary issues
        if (arr[n - 1] != arr[n - 2]) {
            return arr[n - 1];
        }
        
        // Trim search space to avoid out-of-bounds checks inside the loop
        int low = 1, high = n - 2;
        
        while (low <= high) {
            int mid = low + (high - low) / 2;
            
            // 1. Check if mid is the single element
            if (arr[mid] != arr[mid + 1] && arr[mid] != arr[mid - 1]) {
                return arr[mid];
            }
            
            // 2. Determine which half we are on and eliminate accordingly
            // Left half condition: 
            // - mid is even and arr[mid] == arr[mid + 1]
            // - OR mid is odd and arr[mid] == arr[mid - 1]
            if ((mid % 2 == 0 && arr[mid] == arr[mid + 1]) || 
                (mid % 2 == 1 && arr[mid] == arr[mid - 1])) {
                // We are on the left half; single element is on the right
                low = mid + 1;
            } else {
                // We are on the right half; single element is on the left
                high = mid - 1;
            }
        }
        
        return -1; // Dummy return statement for compiler compliance
    }
}

7. Summary and Key Takeaways

• Problem Nature: Finding a unique single element in a sorted array filled with pairs.
• Linear Approach Limitation: Scanning via a for-loop results in an inefficient $O(n)$ time complexity.
• Binary Search Optimization: By leveraging the sorted property and index parity, we can achieve an optimal $O(\log n)$ time complexity.
• Index Parity Insight: Before the single element, pairs start at even indices and end at odd indices. After the single element, this pattern inverts.
• Writing Clean Code: Manually validating boundary elements (0 and n - 1) allows us to eliminate complex conditional boundary checks inside the binary search loop.
• Time Complexity: $O(\log n)$ due to dividing the search space in half at each iteration.
• Space Complexity: $O(1)$ auxiliary space as no additional data structures are used.