Find Single Element in Sorted Array Optimal Binary Search Approach

You are given a sorted array where every element appears exactly twice, except one element that appears only once. Your task is to find and return the single non-repeating element.

Note: The array is sorted in non-decreasing order. There will always be exactly one such unique element in the array.

If the array is empty, return null or an appropriate message indicating that the array is invalid.

Understanding the Problem

We are given a sorted array where every element appears exactly twice, except for one element that appears only once. Our goal is to find that single, unique element.

Because the array is sorted and all duplicate elements are grouped together, we can make use of this structure to efficiently locate the single element using binary search, achieving O(log n) time complexity instead of scanning the entire array.

Step-by-Step Solution with Example

step 1: Visualize with an example

Let’s consider the array: [1, 1, 2, 2, 3, 4, 4, 5, 5]. Here, every element appears twice except for 3.

step 2: Understand pairing pattern

Normally, in a perfectly paired array like [a, a, b, b, c, c], the first of each pair is found at an even index, and its duplicate at the next (odd) index.

But once a single unique element is introduced, this pattern breaks at that point. After the unique element, all pairs shift: now the first of a pair appears at an odd index.

step 3: Use binary search

We apply binary search to find where this shift in pattern occurs. At each step:

• We compute the mid index.
• If mid is even and nums[mid] == nums[mid+1], it means the unique element is on the right side.
• If mid is odd and nums[mid] == nums[mid-1], again, the unique is on the right.
• Otherwise, the unique is on the left side (including mid).

step 4: Apply on the example

Let’s walk through the binary search on [1, 1, 2, 2, 3, 4, 4, 5, 5]:

1. Start: low = 0, high = 8
2. Mid = (0+8)//2 = 4 → nums[4] = 3
3. Check neighbors: nums[3] = 2 and nums[5] = 4 → both are not equal to 3
4. Hence, 3 is the unique element — we’ve found our answer!

step 5: Final implementation logic

def singleNonDuplicate(nums):
    low, high = 0, len(nums) - 1
    while low < high:
        mid = (low + high) // 2
        if mid % 2 == 1:
            mid -= 1  # make mid even
        if nums[mid] == nums[mid + 1]:
            low = mid + 2
        else:
            high = mid
    return nums[low]

Edge Cases

• Single element array: e.g. [7] → return 7 directly.
• Single element at the start: e.g. [2, 3, 3, 4, 4] → 2 is unique, since it’s not equal to the next.
• Single element at the end: e.g. [1, 1, 2] → 2 is unique, as it doesn’t match the previous.
• Empty array: Invalid input, return null or raise an exception.

Finally

This solution is efficient and leverages the sorted structure and pairing pattern of the array. Understanding the even-odd index behavior before and after the unique element is key to narrowing the search.

Always validate the input and handle edge cases before proceeding with the binary search. If the array was unsorted or had more than one unique element, this approach wouldn’t work — a different method like XOR-based scanning would be needed.

1. Initialize start = 0 and end = n - 2.
2. While start ≤ end:
3. → Compute mid = start + (end - start) / 2.
4. → Check if mid is even:
5. → If arr[mid] == arr[mid + 1], the unique element is on the right → start = mid + 2.
6. → Else, the unique element is on the left → end = mid.
7. → If mid is odd:
8. → If arr[mid] == arr[mid - 1], the unique element is on the right → start = mid + 1.
9. → Else, the unique element is on the left → end = mid - 1.
10. After the loop, the start index points to the single element.

O(1)

Explanation: Only a few variables (start, end, mid) are used regardless of input size.