Single Non-Duplicate in Sorted Array

XXX. Single Non-Duplicate in Sorted Array

Binary Search

Problem Statement:

Given a sorted array of integers where every element appears exactly twice except for one element which appears only once, find the single element that appears only once.

The solution must run in O(log n) time and use O(1) extra space.

Algorithm:

The solution uses a binary search approach to efficiently locate the single element. The key insight is that the array is divided into two halves:

1. Calculate the middle index mid of the current range.
2. Check if nums[mid] is the single element by verifying that it is not equal to its neighbors.
3. If nums[mid] matches its left neighbor nums[mid - 1]:
   • If the number of elements from low to mid is even, the single element must lie in the left half. Move high to mid - 2.
   • Otherwise, the single element lies in the right half. Move low to mid + 1.
4. If nums[mid] matches its right neighbor nums[mid + 1]:
   • If the number of elements from mid to high is even, the single element must lie in the right half. Move low to mid + 2.
   • Otherwise, the single element lies in the left half. Move high to mid - 1.
5. If neither condition applies, nums[mid] is the single element. Return it.

Complexity:

Time Complexity: O(log n), where n is the size of the input array. The array is divided in half at each step.
Space Complexity: O(1), as no additional data structures are used.

Java Implementation:

public int singleNonDuplicate(int[] nums) {
    int low = 0, high = nums.length - 1; // Define search range

    while (low <= high) {
        int mid = low + (high - low) / 2; // Calculate the middle index
        boolean halvesAreEven = (high - mid) % 2 == 0; // Check if right half has an even number of elements

        // Case 1: nums[mid] matches nums[mid - 1]
        if (mid > 0 && nums[mid - 1] == nums[mid])
            if (halvesAreEven) high = mid - 2; // Single element lies in left half
            else low = mid + 1; // Single element lies in right half

        // Case 2: nums[mid] matches nums[mid + 1]
        else if (mid < nums.length - 1 && nums[mid + 1] == nums[mid])
            if (halvesAreEven) low = mid + 2; // Single element lies in right half
            else high = mid - 1; // Single element lies in left half

        // Case 3: nums[mid] is the single element
        else return nums[mid];
    }

    return -1; // This line should never be reached if input guarantees a solution
}

Explanation:

The binary search algorithm exploits the sorted property of the array and the fact that elements appear exactly twice except for one. By calculating the middle index and comparing the element with its neighbors, the algorithm narrows the search range based on whether the halves of the array contain an even or odd number of elements.

• If nums[mid] matches nums[mid - 1], the single element must lie in the half where the count of elements excluding the matching pair is odd.
• Similarly, if nums[mid] matches nums[mid + 1], the single element must lie in the half with an odd number of elements.
• If neither condition applies, nums[mid] is the single element, and it is returned immediately.