Problem Description

• 540 Single Element in a Sorted Array

The "Single Element in a Sorted Array" problem asks you to find the single element that appears exactly once in a sorted array where all other elements appear exactly twice.

Key Constraints:

• The array is sorted in ascending order
• Every element appears exactly twice, except for one element that appears once
• The array length is always odd (since 2n + 1 elements total)
• Must solve in O(log n) time complexity

Example: [1,1,2,3,3,4,4,7,7,8,8]

• All elements appear twice except 2
• Result: 2

Naive Approach: Linear scan would be O(n), but we need O(log n), which suggests binary search.

Algorithm Walkthrough

This solution uses binary search with a clever insight about how the single element affects the pairing pattern in a sorted array.

Key Insight: Pairing Pattern

In a sorted array where all elements appear twice except one:

Before the single element:

• Elements are paired as: [a,a,b,b,c,c,...]
• At even indices: nums[i] == nums[i+1]
• At odd indices: nums[i] == nums[i-1]

After the single element:

• The pairing shifts: [...x,y,y,z,z,...]
• At even indices: nums[i] == nums[i-1] (pairing is shifted)
• At odd indices: nums[i] == nums[i+1] (pairing is shifted)

Binary Search Logic

The algorithm determines which side of the array contains the single element by checking the pairing pattern at the middle index:

Condition Check:

(mid % 2 == 0 && nums[mid] == nums[mid + 1]) || 
(mid % 2 == 1 && nums[mid] == nums[mid - 1])

This condition is true when the pairing is normal (single element is to the right):

• Even index (mid % 2 == 0): Should pair with next element (nums[mid] == nums[mid + 1])
• Odd index (mid % 2 == 1): Should pair with previous element (nums[mid] == nums[mid - 1])

Search Direction:

• If condition is true: Normal pairing → single element is on the right → left = mid + 1
• If condition is false: Abnormal pairing → single element is on the left (or at mid) → right = mid

Example Trace

For array [1,1,2,3,3,4,4,7,7,8,8] (single element is 2 at index 2):

Initial: left=0, right=10

Iteration 1:
- mid = 5, nums[5] = 4
- mid % 2 == 1 (odd), nums[5] == nums[4] (4 == 3? No)
- Condition false → right = 5

Iteration 2:
- mid = 2, nums[2] = 2
- mid % 2 == 0 (even), nums[2] == nums[3] (2 == 3? No)
- Condition false → right = 2

Iteration 3:
- left = 0, right = 2
- mid = 1, nums[1] = 1
- mid % 2 == 1 (odd), nums[1] == nums[0] (1 == 1? Yes)
- Condition true → left = 2

Final: left = right = 2, return nums[2] = 2

Complexity Analysis

Time Complexity: O(log n)

• Binary search: Each iteration halves the search space
• Constant operations: Each iteration performs O(1) array access and comparisons
• Total iterations: log₂(n) iterations

Space Complexity: O(1)

• Variables only: Uses only a constant number of variables (left, right, mid)
• No additional data structures: No extra arrays or recursion stack

Full Solution

This solution elegantly uses binary search by recognizing that the single element disrupts the regular pairing pattern in a sorted array. The key insight is that before the single element, pairs follow a predictable pattern based on even/odd indices, while after the single element, this pattern is shifted.

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

The algorithm efficiently narrows down the search space by determining which side of the array contains the single element based on whether the pairing pattern at the middle index is normal or disrupted. This achieves the required O(log n) time complexity while using only O(1) space.