⚡Flashcard Drill➔
NeetCode #272LC-540MediumBinary Search
← Back to All Problems

#272 · #540 · Single Element in a Sorted Array(有序数组中的单一元素)

📌 Problem Statement & Constraints

You are given a sorted array of integers where every element appears exactly twice except one element which appears once. Return the single element. Constraints: 1 <= nums.length <= 10^5, nums.length is odd, 0 <= nums[i] <= 10^5. The solution must run in O(log n) time and O(1) space.

💡 Core Algorithmic Approaches

  1. In a paired array, elements at even indices start a pair. Once the single element is passed, the parity flips.
  2. Binary search while keeping mid at an even index: if nums[mid] == nums[mid+1], the single element is to the right; otherwise it is at or to the left of mid.
  3. Normalising mid to an even index is what keeps the pairing alignment valid throughout the search.
  4. The loop converges on the index of the single element.

💻 Benchmark Python3 Implementation

class Solution:
    def singleNonDuplicate(self, nums: List[int]) -> int:
        lo, hi = 0, len(nums) - 1
        while lo < hi:
            mid = (lo + hi) // 2
            if mid % 2 == 1:           # keep mid at an even index
                mid -= 1
            if nums[mid] == nums[mid + 1]:
                lo = mid + 2           # the single element is to the right
            else:
                hi = mid               # it is at or left of mid
        return nums[lo]


# XOR variant: O(n) time but O(1) space and one line
class Solution2:
    def singleNonDuplicate(self, nums: List[int]) -> int:
        res = 0
        for x in nums:
            res ^= x
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(log n) for the binary search; O(n) for the XOR variant.
💾 Space Complexity
O(1) for both.

⚠️ Interview Pitfalls & Follow-ups

  • Not normalising mid to an even index: the pairing parity would be wrong and the search direction inverted.
  • Using lo = mid + 1 on a match: the pair spans two indices, so the next candidate is mid + 2.
  • Using the XOR variant: it is O(n), which the O(log n) requirement forbids (though it is a good sanity check).
  • Assuming the array is 0-indexed with pairs starting at 0: this holds because the array length is odd and all other elements are paired.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Binary Search Problems