Single Element in a Sorted Array

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(int[] nums) {
    int l = 0;
    int r = nums.length - 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 the 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 the search space. If the middle element is even and matches the next element, it means the single element must be on the right side. If it doesn’t match, we adjust our search to the left. This continues until we find our lonely number.

Time and Space Complexity

Complexity	Details
Time Complexity	O(log n) - Because we are using binary search, the time complexity is logarithmic.
Space Complexity	O(1) - We are using a constant amount of space, regardless of the input size.

Real-World Example

Think of a scenario where you’re organizing a family reunion. Everyone is paired up for a group photo, but your cousin Timmy decided to bring his pet iguana instead of a plus one. While everyone else is in pairs, Timmy stands out with his scaly friend. In the array, Timmy represents the single element, and your task is to spot him among the pairs!