Single Element in a Sorted Array

Explore More Solutions

Code Solution


class Solution:
    def singleNonDuplicate(self, nums: list[int]) -> int:
        l = 0
        r = len(nums) - 1

        while l < r:
            m = (l + r) // 2
            if m % 2 == 1:
                m -= 1
            if nums[m] == nums[m + 1]:
                l = m + 2
            else:
                r = m

        return nums[l]

Problem Description

Ah, the classic "Single Element in a Sorted Array" problem! Imagine you’re at a party, and everyone is dancing in pairs. But wait! There’s that one awkward person who decided to come solo. Your job, should you choose to accept it, is to find that lone wolf among the pairs.

In this problem, you’re given a sorted array where every element appears twice, except for one. Your mission, should you choose to accept it, is to identify that single element. It’s like playing hide and seek, but instead of hiding, the number is just chilling out alone, waiting for you to find it.

Approach Explanation

The provided code uses a binary search approach to efficiently find the single element. Here’s a brief breakdown of the approach:

Initialization: Two pointers, l (left) and r (right), are initialized to the start and end of the array.
Binary Search: The loop continues until l is less than r. The middle index m is calculated.
Adjusting Middle Index: If m is odd, it’s adjusted to be even. This ensures that pairs are always checked correctly.
Checking Pairs: If the element at m matches the next element, it means the single element must be to the right, so l is updated. Otherwise, the single element is to the left, and r is updated.
Return Result: Finally, when the loop ends, l points to the single element, which is returned.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(log n)
Space Complexity	O(1)

Real-World Example

Think of a concert where everyone is singing in pairs, but one person forgot their partner. You’re tasked with finding that solo singer. Just like in the array, where every number has a buddy except for one, you can use the same binary search technique to quickly locate the lone singer without having to listen to every duet.