Single Element in a Sorted Array – C++ Solution

Explore More Solutions:

Problem Description

Ah, the classic “Single Element in a Sorted Array” problem! Imagine you’re at a party, and everyone is dancing in pairs. Suddenly, you notice one person awkwardly standing alone, sipping their drink. That’s your single element! In this problem, you’re given a sorted array where every element appears twice, except for one lonely soul that appears just once. Your mission, should you choose to accept it, is to find that single element.

So, if you have an array like [1, 1, 2, 2, 3, 3, 4, 4, 5], you’ll need to identify that one unique number, which in this case is 5. Easy peasy, right?

Code Solution


class Solution {
 public:
  int singleNonDuplicate(vector& nums) {
    int l = 0;
    int r = nums.size() - 1;

    while (l < r) {
      int m = (l + r) / 2;
      if (m % 2 == 1)
        --m;
      if (nums[m] == nums[m + 1])
        l = m + 2;
      else
        r = m;
    }

    return nums[l];
  }
};

Approach

The approach used in this code is a binary search technique. The idea is to leverage the sorted nature of the array. By checking pairs of elements, we can effectively narrow down our search space. If the middle element is even and matches the next element, we know the single element must be to the right. If it doesn’t match, we search to the left. This continues until we find our lonely number.

Time and Space Complexity

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

Real-World Example

Think of a group of friends who always go out in pairs. One day, they decide to go to a concert, but one friend gets lost in the crowd. You need to find that friend who is not paired up with anyone else. Just like in our problem, you can use the same logic to identify that single friend amidst the crowd!