266. Single Element in a Sorted Array

Before the single element, pairs start at even indices (0-1, 2-3, ...). After it, that parity breaks. Binary search for where the even-index pairing first fails.

Parity of pair starts

Without the singleton, every pair occupies indices (2k, 2k+1). The single element shifts everything after it by one, breaking that alignment. So at an even mid: if nums[mid] == nums[mid+1], the pairing still holds up to here → the singleton is to the right (lo = mid + 2); otherwise it's at or before mid (hi = mid).

lo, hi = 0, n-1
while lo < hi:
    mid = (lo+hi)//2; if mid odd: mid -= 1
    if nums[mid] == nums[mid+1]: lo = mid + 2
    else: hi = mid
return nums[lo]

Worked example

[1,1,2,3,3,4,4,8,8] → converges on index 2 → 2.

Complexity

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

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