Single Element in a Sorted Array — Parity Index Binary Search

Problem 327 · Single Element in a Sorted Array

Difficulty: Medium · Pattern: Parity-Based Binary Search

Every element appears twice except one. Find it in O(log n).

Intuition

Before the single element: pairs are at even-odd indices. After: at odd-even indices. Check parity at mid.

Use even-indexed mid: if nums[mid] == nums[mid+1], single is in right half; else left half.

Solutions

# Python
def singleNonDuplicate(nums):
    lo, hi = 0, len(nums)-1
    while lo < hi:
        mid = lo + (hi-lo)//2
        if mid % 2 == 1: mid -= 1  # make mid even
        if nums[mid] == nums[mid+1]: lo = mid+2  # pair intact, single is right
        else: hi = mid                              # single is mid or left
    return nums[lo]

// Java
public int singleNonDuplicate(int[] nums) {
    int lo=0, hi=nums.length-1;
    while (lo<hi) {
        int mid=lo+(hi-lo)/2;
        if (mid%2==1) mid--;
        if (nums[mid]==nums[mid+1]) lo=mid+2; else hi=mid;
    }
    return nums[lo];
}

Complexity

Time: O(log n)
Space: O(1)