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
- In a paired array, elements at even indices start a pair. Once the single element is passed, the parity flips.
- Binary search while keeping
midat an even index: ifnums[mid] == nums[mid+1], the single element is to the right; otherwise it is at or to the left ofmid. - Normalising
midto an even index is what keeps the pairing alignment valid throughout the search. - 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
midto an even index: the pairing parity would be wrong and the search direction inverted. - Using
lo = mid + 1on a match: the pair spans two indices, so the next candidate ismid + 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.