The Single Element Array: A Binary Search Tale

You just finished a grueling take-home for a senior staff role, spent 6 hours on a distributed consensus algorithm, and now they want you to find the unique number in a sorted array? Seriously? Yes, seriously. This "Single Element in Sorted Array" problem, often disguised as something simple, is a fantastic litmus test for how deeply someone understands binary search and its non-obvious applications. It's not about memorizing the solution; it's about seeing the pattern.

Why This Problem Matters (It's Not Just LeetCode Bingo)

Look, I've sat through enough Google and Meta loops to tell you this: they don't just ask these problems to trip you up. They're looking for clean problem decomposition, edge case thinking, and especially, an intuitive grasp of how to prune search spaces. This particular problem forces you to adapt a classic algorithm, binary search, in a subtle way. A lot of candidates jump to XORing everything – which works, sure, but misses the constraint: "sorted array." That constraint is your biggest hint, and ignoring it is a red flag. It tells the interviewer you're not paying attention to critical information.

The problem statement usually goes like this: you get a sorted array where every element appears twice, except for one element. Find that single element. For example, [1,1,2,3,3,4,4,8,8] should return 2. Your solution needs to be O(log n) time and O(1) space. If you're thinking O(n) or O(n log n), you're probably overcomplicating it, or worse, not leveraging the "sorted" part.

Deconstructing The Problem: Where's The Pattern Break?

Binary search thrives on properties. When you split a sorted array in half, you know something about the halves. Here, the key insight is about parity and pairs. Every number appears twice, which means if you have [1,1,2,2,3,3,4], before the 4, all pairs are complete. The number of elements before any given pair must be even. After the 4, the pattern is broken; the number of elements before any subsequent pair would be odd.

Let's take [1,1,2,3,3,4,4,8,8]. The unique element is 2. If you split this in the middle, say around 3,3, what do you notice? To the left: [1,1,2]. To the right: [4,4,8,8]. The key is that the length of the subarray before the unique element will always be even. The length of the subarray after the unique element will also always be even. It's the number of elements up to a certain point that matters for parity checks.

Consider an array arr with n elements. If arr[mid] is part of a pair, say arr[mid] == arr[mid+1], then you need to figure out which side the unique element is on. If mid is even, and arr[mid] == arr[mid+1], it means this pair starts at an even index. All elements before mid are paired up. The unique element must be in the right half. If mid is odd, and arr[mid] == arr[mid+1], then the pair starts at an odd index. This means arr[mid-1] must be the unique element, or the unique element is to the left of mid-1. This is where it gets tricky and often misunderstood.

The Correct Binary Search Adaptation

Instead of worrying about mid being even or odd, think about the start of a pair. If arr[mid] == arr[mid+1] (assuming mid+1 is in bounds), this is a pair. The crucial check: is the count of elements before this pair even or odd? If arr[mid] is arr[mid+1], and mid is an even index, then the unique element must be in [mid+2, high]. Why? Because arr[0] to arr[mid+1] forms complete pairs. The single element can't be there. If arr[mid] is arr[mid+1], and mid is an odd index, then the unique element must be in [low, mid-1]. Why? Because arr[0] to arr[mid-1] has an odd number of elements. The single element must be in that prefix.

What if arr[mid] is arr[mid-1] (assuming mid-1 is in bounds)? Similar logic: If arr[mid] is arr[mid-1], and mid is an even index, then the unique element is in [low, mid-2]. If arr[mid] is arr[mid-1], and mid is an odd index, then the unique element is in [mid+1, high].

This parity check on mid is the core. Let's refine it. We look at nums[mid].

1. If nums[mid] == nums[mid-1]:
   • If mid is odd, then the paired element is nums[mid-1]. All elements before nums[mid-1] are paired. So the unique element must be to the right: low = mid + 1.
   • If mid is even, then the paired element is nums[mid-1]. This means nums[mid-1] is at an odd index, and nums[mid] at an even index. This pair started "early." The unique element must be to the left: high = mid - 2.
2. If nums[mid] == nums[mid+1]:
   • If mid is even, then the paired element is nums[mid+1]. All elements before nums[mid] are paired. So the unique element must be to the right: low = mid + 2.
   • If mid is odd, then the paired element is nums[mid+1]. This means nums[mid] is at an odd index, and nums[mid+1] at an even index. This pair starting "early" means the unique element is to the left: high = mid - 1.
3. If nums[mid] is not equal to nums[mid-1] AND not equal to nums[mid+1], then nums[mid] is the single element. Bingo.

You need to handle boundary conditions for mid-1 and mid+1 carefully. What if mid is 0 or n-1? The problem setup guarantees a single unique element, which implies n is always odd. This simplifies things. The edge cases of mid being 0 or n-1 often mean nums[mid] is the answer anyway since it can't form a pair on both sides.

def singleNonDuplicate(nums: list[int]) -> int:
    low, high = 0, len(nums) - 1

    while low < high:
        mid = (low + high) // 2

        # Check if mid is unique
        # This is the easiest case: it's not equal to its neighbors
        # We need to ensure mid-1 and mid+1 are in bounds for this check
        # But the loop condition (low < high) and problem constraints often simplify this
        # For a truly robust check:
        # if (mid == 0 or nums[mid] != nums[mid-1]) and \
        #    (mid == len(nums) - 1 or nums[mid] != nums[mid+1]):
        #    return nums[mid] 
        # However, the parity logic below actually naturally covers this when the search space collapses.

        # If mid is even, its pair should be at mid+1
        # If mid is odd, its pair should be at mid-1
        # We adjust mid to always point to the start of a potential pair for simpler logic
        if mid % 2 == 1: # If mid is odd, make it even by decrementing
            mid -= 1    # Now mid is at an even index

        # Now mid is guaranteed to be an even index.
        # Check if nums[mid] forms a pair with nums[mid+1]
        if nums[mid] == nums[mid+1]:
            # The pair (nums[mid], nums[mid+1]) is a normal pair.
            # All elements before this pair are also normal pairs.
            # So the unique element must be to the right of this pair.
            low = mid + 2
        else:
            # nums[mid] != nums[mid+1]. This means nums[mid] is either the unique element
            # or it's the first element of a pair where the second element is not nums[mid+1]
            # (which implies the unique element is to its left).
            # The unique element is in the left half, including or before mid.
            high = mid
            
    return nums[low] # When low == high, we've found the single element

This simplified parity-based approach often clicks for people. The key is to normalize mid to an even index. If mid is odd, think of mid-1 as the start of its pair. If nums[mid-1] == nums[mid], then mid-1 is an even index, and that pair starts correctly. If not, the unique element is to the left. It's about maintaining the invariant: the unique element is in the current [low, high] range.

Why Binary Search is Brutal (and Beautiful)

Binary search solutions, especially modified ones, often feel like magic. You're constantly halving the problem space, which is why it's so efficient. But the devil is always in the details:

• Off-by-one errors: The low, high, mid assignments (mid+1, mid-1, mid+2, mid-2) are notoriously easy to mess up.
• Loop termination: low < high vs. low <= high changes behavior for where low or high lands as the answer.
• Edge cases: len(nums) == 1, len(nums) being odd, the unique element being at the start or end.

For this problem, because n is always odd, len(nums) == 1 is an implicit base case (the loop won't run, low is 0, nums[0] is returned). If the unique element is at the end, low will eventually converge to that index. If it's at the start, high will converge. The mid % 2 == 1 adjustment ensures that mid always points to an index that could be the start of a pair. This simplifies the logic dramatically.

Interviewer Follow-ups: Beyond The Basic Solution

An interviewer won't just let you off with the O(log n) solution. They'll push.

1. What if the array wasn't sorted?
   • "Then I'd use XOR. Initialize res = 0. Iterate through the array res ^= num. The final res is the answer. That's O(n) time, O(1) space. We lose the O(log n) advantage from sorting because the structure isn't there."
2. What if there were two unique elements?
   • "That's a different problem. You'd still use XOR for O(n). XOR all elements together, you get X = A ^ B. Then find the rightmost set bit in X. Partition the original array into two groups: those with that bit set, and those without. XOR elements in each group separately. One group will yield A, the other B. Still O(n) time, O(1) space."
3. Can you generalize this for k duplicates, where k is odd except for one element?
   • "That's tricky for binary search. If k is a fixed odd number (e.g., 3 duplicates), you could try to adapt, but it becomes much harder to maintain the parity invariant. A hash map (Counter in Python) storing counts would be O(n) time and O(n) space. You could also use bit manipulation with 32-bit integers: count the set bits at each position across all numbers. If the count of a bit position modulo k is non-zero, that bit is set in the unique number. This is O(n * log(max_val)) time and O(1) space (if max_val fits in a fixed number of bits)."

These follow-ups differentiate a candidate who just memorized the solution from one who deeply understands the underlying principles and trade-offs. Don't just give the answer; explain why something changes or why an alternative is better/worse under different constraints.

Common Pitfalls and How to Avoid Them

• Forgetting the "sorted" constraint: The easiest way to derail the interview. Your initial thought should always be: how can I use this property?
• Not testing enough edge cases: What if the array is [1,2,2]? [1,1,2]? [1]? Make sure your mid calculations and boundary adjustments correctly handle these.
• Incorrectly updating low and high: This often leads to infinite loops or skipping the correct answer. Draw out the array, mark low, high, mid, and trace how they move.
• Overcomplicating the parity check: The mid % 2 == 1 adjustment simplifies the mental model significantly. Stick to one pattern. My example code makes mid always an even index before the comparison, which is a powerful simplification.

The single element in a sorted array problem is a classic for a reason. It's simple enough to be solvable, but nuanced enough to reveal a candidate's understanding of binary search variations. Practice this one a few times, trace it with examples, and internalize the parity logic. It'll pay dividends.

Ready to Ace Your Next Interview?

Practice with AI-powered mock interviews tailored to your target role and company. Start Practicing for Free | Explore Interview Prep