Find the element that appears once in a sorted array, and the rest element appears twice (Binary search)

Problem Overview

LeetCode Question: Single Element in a Sorted Array

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.

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

Example:

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

The challenge is to identify the single element in a sorted array with linear time complexity O(log n) and constant space complexity, utilizing binary search.

Understanding the Problem

This problem presents a sorted integer array where every integer appears exactly twice, except for one integer that appears only once. The task is to find this single unique integer efficiently.

The sorted nature of the array is a hint that binary search can be applied here. The goal is not just to identify the unique element, but to do so in a time complexity of O(log n), which suggests that linear-time solutions are not optimal due to constraints.

Key DSA Concepts and Theory

Binary Search

Binary Search is a classic algorithm that efficiently finds a target value within a sorted array. The key idea is to repeatedly divide the search interval in half, ruling out the half where the target cannot lie.

• Algorithm Efficiency: O(log n) time complexity.
• Space Complexity: O(1) when implemented iteratively.

How Binary Search Translates Here

In this problem's context, binary search will be used not to find a specific value but to find the index where the pattern of duplicates is broken due to our single element. Since every pair of numbers is orderly, the subarray with index up to the single element will have the property where the first occurrence of any number will always be at an even index.

Solution Approach

Step-by-Step Solution

1. Initialization:

   • Set two pointers: low at the start (0) and high at the end (n-1) of the array.

2. Binary Search:

   • While low < high, calculate the midpoint mid using low + (high - low) / 2.
   • Check the pattern:
     • Ensure that mid is an even index.
     • Compare nums[mid] with nums[mid + 1].
     • If they are equal, our single element lies in the right half, so increment low = mid + 2.
     • If not, the single element is in the left half, so adjust high = mid.
   • Continue until low converges on the unique element.

3. Conclusion:

   • The loop exits when low == high, and this index low corresponds to the single element.

Code Implementation

C++ Code

int singleNonDuplicate(vector<int>& nums) {
    int low = 0, high = nums.size() - 1;
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (mid % 2 == 1) mid--;  // Ensure mid is even
        if (nums[mid] == nums[mid + 1]) {
            low = mid + 2;
        } else {
            high = mid;
        }
    }
    return nums[low];
}

Java Code

public int singleNonDuplicate(int[] nums) {
    int low = 0, high = nums.length - 1;
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (mid % 2 == 1) mid--;  // Ensure mid is even
        if (nums[mid] == nums[mid + 1]) {
            low = mid + 2;
        } else {
            high = mid;
        }
    }
    return nums[low];
}

Time and Space Complexity Analysis

• Time Complexity: O(log n) due to the binary search approach which divides the search space in half each step.
• Space Complexity: O(1), as no additional space is used outside of simple variables for binary search indices.

Common Mistakes to Avoid

• Failing to ensure mid is always an even index can lead to index errors.
• Misunderstanding the conditions to adjust low and high, which can lead to infinite loops or incorrect results.

Similar Problems on LeetCode

1. Problem 153: Find Minimum in Rotated Sorted Array
2. Problem 154: Find Minimum in Rotated Sorted Array II
3. Problem 162: Find Peak Element

Additional Resources and References

• Binary Search Wikipedia
• LeetCode Discuss - Single Element in a Sorted Array

By understanding the interplay of patterns and binary search, this problem can be efficiently solved through careful attention to the constraints and properties induced by the array's sorting.