540. Single Element in a Sorted Array

This problem looks simple at first glance, but it is a classic example of how problem constraints fundamentally change the expected solution. While finding a unique element is trivial in an unsorted array, the fact that the array is sorted and that every other element appears exactly twice is not incidental it is the core of the problem.

Interviewers use this question to test whether you can exploit ordering and structure to move beyond linear scans.

Problem statement

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

Constraints:

• 1 <= nums.length <= 10^5
• 0 <= nums[i] <= 10^5

Examples

Why a naive approach is insufficient

A linear scan or an XOR-based solution can correctly identify the single element in O(n) time. However, the problem explicitly requires an O(log n) solution, which immediately rules out any linear-time approach.

This constraint is a strong signal from the problem statement:

You are expected to leverage the fact that the array is sorted and apply binary search. As a result, linear solutions, while correct, are not acceptable in an interview setting and are not worth exploring further.

Intuition

To understand how to apply binary search, let’s reason about how pairs behave in a sorted array.

In a perfectly paired array (with no single element yet), every number appears exactly twice in a predictable pattern:

• The first occurrence of a pair appears at an even index
• The second occurrence appears at the next odd index

This creates a clean even–odd pairing across the array.

Now introduce a single element that appears only once.

From that point onward, the pairing pattern breaks. All subsequent pairs shift by one position:

• Pairs that previously started at even indices now start at odd indexes.

This index shift is the critical observation that allows us to use binary search instead of scanning the entire array.

Optimized approach using Binary Search

We solve this problem using binary search by exploiting how pairs are arranged in a sorted array.

At any index mid, the expected pairing depends on whether mid is even or odd. If mid is even, the correct pair should satisfy nums[mid] == nums[mid + 1]. If mid is odd, the correct pair should satisfy nums[mid] == nums[mid - 1].

When this expected pairing holds, it means all elements up to mid are correctly paired, and the single element must lie on the right side. When the pairing breaks, the single element lies on the left side (or at mid itself).

By repeatedly checking this pairing condition and narrowing the search space accordingly, we preserve the pairing invariant and reduce the problem size by half at each step. This allows us to locate the single element in O(log n) time using binary search.

Step-by-step algorithm

1. Initialize two pointers left and right at both ends of the array nums:
2. While left < right:
   1. Compute mid = (left + right) // 2
   2. If mid is odd, decrement it by 1 to make it even.
   3. Compare the pair using nums[mid] == nums[mid + 1]:
      1. If this is True, move left = mid + 2 which means the single element lies to the right side.
      2. Otherwise, move right = mid which means the single element lies on the left side or at mid.
3. Once the iteration ends, return nums[left] which holds the single element.

Let’s look at the following illustration to get a better understanding of the solution:

1 / 6

Code implementation

Let’s look at the code for this solution below:

def singleNonDuplicate(nums):
    left, right = 0, len(nums) - 1

    while left < right:
        mid = (left + right) // 2

        # Ensure mid is even
        if mid % 2 == 1:
            mid -= 1

        if nums[mid] == nums[mid + 1]:
            # Single element is on the right
            left = mid + 2
        else:
            # Single element is on the left or at mid
            right = mid

    return nums[left]


def main():
    testCases = [
        [5, 5, 9, 9, 12, 14, 14, 18, 18],
        [2, 2, 4, 4, 6, 7, 7, 9, 9],
        [1, 1, 3, 3, 8, 10, 10, 11, 11],
        [4, 4, 6, 6, 7, 9, 9],
        [0, 0, 1, 1, 2, 3, 3]
    ]

    for i, nums in enumerate(testCases, 1):
        print(i, ".\t Input nums = ", nums, sep="")
        print("\t Single element: ", singleNonDuplicate(nums), sep="")
        print("-" * 75)

 
if __name__ == "__main__":
    main()

Time complexity

Each iteration halves the search space, as expected from binary search. So, the overall time complexity of the algorithm becomes O(log n) as required by the problem statement.

Space complexity

The algorithm only uses a constant extra space. So, the space complexity is O(1).

Common pitfalls and interview tips

• Forgetting to normalize mid: If mid is odd, and you compare mid with mid + 1, the pairing logic breaks.
• Using XOR without reading constraints: XOR works, but it violates the O(log n) requirement. Interviewers will reject it.
• Overthinking edge cases: Binary search naturally handles cases where the single element is:
  • At the beginning
  • At the end
  • In the middle