540. Single Element in a Sorted Array - Detailed Explanation

Problem Statement

You are given a sorted array of integers where every element appears exactly twice except for one element that appears only once. Your task is to find that single element that does not have a duplicate.

Example 1

• Input: nums = [1,1,2,3,3,4,4,8,8]
• Output: 2
• Explanation:
  In the array, every number appears twice except for 2, which appears only once.

Example 2

• Input: nums = [3,3,7,7,10,11,11]
• Output: 10
• Explanation:
  All elements appear in pairs except for 10.

Constraints

• The array is sorted in non-decreasing order.
• Every element except one appears exactly twice.
• The array length is odd.

Hints and Intuition

• Hint 1:
  A straightforward approach is to use the XOR operation. Since (a \oplus a = 0) and XOR is commutative, XOR-ing all numbers will cancel out the numbers that appear twice, leaving the single number.

• Hint 2:
  Because the array is sorted, you can use a binary search approach to achieve a more efficient solution (O(log n)). Notice that before the single element, pairs start at even indices; after the single element, the pairing order flips. Use this observation to decide which half of the array to search.

• Hint 3:
  Check the index of the mid element:

  • If the mid index is even and its neighbor (mid + 1) is the same, the single element must be in the right half.
  • Otherwise, it’s in the left half (including possibly at mid).

Detailed Approaches

Approach A: XOR (Brute Force)

• Idea:
  XOR all elements together. The duplicates cancel out, and the result is the single element.
• Pros:
  Very simple and runs in O(n) time with O(1) space.
• Cons:
  Although linear, it doesn’t take advantage of the fact that the array is sorted.

Approach B: Binary Search (Optimal)

• Idea:
  Use binary search to locate the single element by leveraging the sorted order:
  1. Set left to 0 and right to the last index.
  2. Compute mid as the middle index. To ensure comparisons are made on the first element of a pair, adjust mid to be even.
  3. If nums[mid] equals nums[mid+1], it means the pair is valid and the single element is on the right side; move left to mid + 2.
  4. Otherwise, the single element lies on the left (or could be at mid), so move right to mid.
  5. Continue until left equals right, which will be the single element.
• Pros:
  Takes advantage of the sorted property, achieving O(log n) time complexity.
• Cons:
  Requires careful index handling and even/odd adjustments.

Step-by-Step Walkthrough (Binary Search)

Consider Example 1: nums = [1,1,2,3,3,4,4,8,8].

1. Initialization:

   • left = 0, right = 8.

2. First Iteration:

   • Compute mid = (0 + 8) // 2 = 4.
   • Make sure mid is even; if it’s not, adjust it. In this case, 4 is even.
   • Compare nums[4] and nums[5]: they are 3 and 4 respectively, so they are not equal.
   • This means the single element lies to the left of mid (including mid), so set right = mid = 4.

3. Second Iteration:

   • Now, left = 0 and right = 4.
   • Compute mid = (0 + 4) // 2 = 2 (even).
   • Compare nums[2] and nums[3]: they are 2 and 3. Since they are not equal, the single element is at mid or to the left.
   • Set right = mid = 2.

4. Third Iteration:

   • Now, left = 0 and right = 2.
   • Compute mid = (0 + 2) // 2 = 1. Since 1 is odd, adjust mid to 0 (the even index).
   • Compare nums[0] and nums[1]: they are both 1, so the single element is to the right.
   • Set left = mid + 2 = 2.

5. Conclusion:

   • Now, left == right == 2.
   • Return nums[2], which is 2.

Code Implementation

Python Implementation (Binary Search)