540. Single Element in a Sorted Array

Intuition

In a sorted array where every element appears exactly twice except one, the pairs are positioned such that:

• Before the single element, the first instance of a pair appears at even indices.

• After the single element, the first instance of a pair appears at odd indices.

By checking index parity and using binary search, we can determine which side the single element lies on and reduce our search space efficiently.

Complexity

Space Complexity	Time Complexity
$\text{O}(1)$	$\text{O}(\log{N})$

Code

public int singleNonDuplicate(int[] nums) {
    int left = 0, right = nums.length - 1;

    // If array has only one element
    if (right == 0) return nums[0];

    while (left <= right) {
        int mid = (left + right) >> 1;

        // Check if nums[mid] is the unique element
        boolean isDifferentFromLeft = (mid - 1 < 0) || (nums[mid] != nums[mid - 1]);
        boolean isDifferentFromRight = (mid + 1 >= nums.length) || (nums[mid] != nums[mid + 1]);

        if (isDifferentFromLeft && isDifferentFromRight) {
            return nums[mid];
        }

        boolean isMidIndexOdd = (mid % 2 == 1);

        // Check if left side is valid (correct pairing)
        if ((isMidIndexOdd && nums[mid] == nums[mid - 1]) || (!isMidIndexOdd && nums[mid] == nums[mid + 1])) {
            left = mid + 1; // Unique element must be on the right
        } else {
            right = mid - 1; // Unique element must be on the left
        }
    }

    return -1; // Should never reach here for a valid input
}