Problem Statement

You are given a sorted array nums where every element appears exactly twice, except for one element that appears only once.

Return the single element that appears only once.

Constraints:

• Your solution must run in O(log n) time and O(1) space.
• 1 ≤ nums.length ≤ 10^5
• 0 ≤ nums[i] ≤ 10^5

Example 1:

Input: nums = [1,1,2,3,3,4,4,8,8]
Output: 2

Example 2:

Input: nums = [3,3,7,7,10,11,11]
Output: 10

---

Approach to Solve the Problem (Binary Search)

Idea:

• Since the array is sorted and every element except one appears twice:
  • Pairs will be aligned: first occurrence at even index, second occurrence at odd index before the single element.
  • After the single element, the alignment flips: first occurrence at odd index, second at even index.
• This pattern allows binary search to find the single element in O(log n) time.

Steps:

1. Initialize low = 0 and high = nums.length - 1.
2. While low < high:
   • Find mid = low + (high - low) / 2.
   • Make mid even if it’s odd (mid ^= 1) to always compare with its pair.
   • If nums[mid] == nums[mid + 1] → single element is after mid → low = mid + 2
   • Else → single element is before or at mid → high = mid
3. Return nums[low].

Why it works:

• The binary search exploits the pair alignment pattern.
• Time complexity is O(log n), space O(1).

---

Java Code Solution (Binary Search)

public class SingleElementSortedArray {

    public static int singleNonDuplicate(int[] nums) {
        int low = 0, high = nums.length - 1;

        while (low < high) {
            int mid = low + (high - low) / 2;
            
            // Ensure mid is even
            if (mid % 2 == 1) mid--;

            if (nums[mid] == nums[mid + 1]) {
                low = mid + 2; // single element is after mid
            } else {
                high = mid;    // single element is at or before mid
            }
        }

        return nums[low];
    }

    public static void main(String[] args) {
        int[] nums = {1,1,2,3,3,4,4,8,8};
        int result = singleNonDuplicate(nums);
        System.out.println("Single element: " + result); // Output: 2
    }
}

---

Dry Run Example

Input:

nums = [1,1,2,3,3,4,4,8,8]

Step-by-step Execution:

1. Initialize: low=0, high=8
2. Iteration 1:
   • mid = (0+8)/2 = 4 → even → nums[4]=3, nums[5]=4
   • nums[4] != nums[5] → single element is before or at mid → high=4
3. Iteration 2:
   • mid = (0+4)/2 = 2 → even → nums[2]=2, nums[3]=3
   • nums[2] != nums[3] → single element is before or at mid → high=2
4. Iteration 3:
   • mid = (0+2)/2 = 1 → make even → mid=0 → nums[0]=1, nums[1]=1
   • nums[0] == nums[1] → single element after mid → low = 0+2 = 2
5. low == high == 2 → stop → nums[2]=2 → single element found

---

Textual Diagram for Understanding

Array: [1,1,2,3,3,4,4,8,8]
Indexes:0 1 2 3 4 5 6 7 8

Step 1: mid=4, nums[4]=3, nums[5]=4 → not equal → high=4
Step 2: mid=2, nums[2]=2, nums[3]=3 → not equal → high=2
Step 3: mid=0, nums[0]=1, nums[1]=1 → equal → low=2

Single element at index 2 → 2

---

Complexity Analysis

• Time Complexity: O(log n)
  • Binary search reduces search space by half each iteration.
• Space Complexity: O(1)
  • Only a few variables are used.

---

This binary search approach efficiently finds the single non-duplicate element in a sorted array while maintaining O(log n) time and O(1) space.