Single Element in a Sorted Array

Problem Description:

Given a sorted array of integers where every element appears twice except for one, you need to find that single element that appears only once.

You must perform this search in O(log n) time complexity and O(1) space complexity.

Sample Input and Expected Output:

Input:

nums = [1, 1, 2, 3, 3, 4, 4, 8, 8]

Output:

Single element in the array: 2

Input:

nums = [3, 3, 7, 7, 10, 11, 11]

Output:

Single element in the array: 10

Solution in C++:

We can solve this problem using a binary search algorithm with a slightly modified approach. Since every element appears twice except for the single element, the single element will always be at an odd index if all the elements before it appear in pairs and even index if all the elements before it appear in pairs.

We can use this property to divide the search space by half and find the single element efficiently.

#include <iostream>
#include <vector>

int singleNonDuplicate(std::vector<int>& nums) {
    int left = 0;
    int right = nums.size() - 1;

    while (left < right) {
        int mid = left + (right - left) / 2;

        // Ensure mid is at an even index
        if (mid % 2 != 0) {
            mid--;
        }

        // Check if the single element is on the left side
        if (nums[mid] == nums[mid + 1]) {
            left = mid + 2;
        }
        // Check if the single element is on the right side
        else {
            right = mid;
        }
    }

    return nums[left];
}

int main() {
    std::vector<int> nums1 = {1, 1, 2, 3, 3, 4, 4, 8, 8};
    std::vector<int> nums2 = {3, 3, 7, 7, 10, 11, 11};

    int result1 = singleNonDuplicate(nums1);
    int result2 = singleNonDuplicate(nums2);

    std::cout << "Single element in the array 1: " << result1 << std::endl;
    std::cout << "Single element in the array 2: " << result2 << std::endl;

    return 0;
}

Time Complexity and Space Complexity:

The time complexity of the solution is O(log n), where n is the size of the nums array. This is because we are performing binary search, and at each step, we reduce the search space by half.

The space complexity is O(1) as we are using a constant amount of additional space for variables in the solution, regardless of the size of the input array.