Single Element in a Sorted Array

You are given a sorted array consisting of only integers where every element appears exactly twice, except for one element which appears exactly once. Find this single element that appears only once.

Note: Your solution should run in O(log n) time and O(1) space.

Example 1:

Input: nums = [1,1,2,3,3,4,4,8,8]
Output: 2

Example 2:

Input: nums = [3,3,7,7,10,11,11]
Output: 10

Constraints:

  • 1 <= nums.length <= 10^5
  • 0 <= nums[i] <= 10^5

Binary Search on Evens Indexes Only

The problem can be solved by doing a Binary Search on even indices.

Intuition

The single element is at the first even index not followed by its pair. Consider the following example:

1,1,2,3,3,4,4

Here, the single element is 2 which is present in the 2nd index of the array. If there is a single element in the array then it must be present on any even index on that array. 

After the single element, the pattern changes to being odd indexes followed by their pair. This means that the single element (an even index) and all elements after it are even indexes not followed by their pair. Therefore, given any even index in the array, we can easily determine whether the single element is to the left or to the right.

Algorithm

We need to perform the binary search on that array in such a way thus it will search for event indices only. The last index of an odd-lengthed array is always even, so we can set low and high to be the start and end of the array. We need to make sure that our mid index is always even. We can do this by finding the mid in the usual way as we do in binary search but then decrementing it by 1 if it is odd. This also ensures that if we have an even number of even indexes to search, that we are getting the lower middle (incrementing by 1 here would not work, it’d lead to an infinite loop as the search space would not be reduced in some cases).

Then we check whether or not the mid index is the same as the one after it.

  • If it is, then we know that mid is not the single element, and that the single element must be at an even index after mid. Therefore, we set low to be mid + 2. It is +2 rather than the usual +1 because we want it to point at an even index.
  • If it is not, then we know that the single element is either at mid, or at some index before mid. Therefore, we set high to be mid.

Once low == high, the search space is down to 1 element, and this must be the single element, so we return it.

class Solution {
    public int singleNonDuplicate(int[] nums) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int low = 0;
        int high = nums.length - 1;
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (mid % 2 == 1) {
                mid--;
            }
            if (nums[mid] != nums[mid + 1]) {
                high = mid;
            } else {
                low = mid + 2;
            }
        }
        return nums[low];
    }
}

Complexity Analysis

  • Time Complexity : O(log n/2​) = O(logn). Same as the Binary Search, except we are only doing binary search on half the elements only.
  • Space Complexity : O(1). Same as the other approaches. We are only using constant space to keep track of where we are in the search.

Categories: Binary Search

Tagged as: ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s