Single Element in a Sorted Array

class Solution {
public:
    int findSingleElement(vector<int>& arr) {
        int start = 0;
        int end = arr.size() - 1;
        while (start < end) {
            int middle = start + (end - start) / 2;
            if (middle % 2 == 1) middle--;
            if (arr[middle] == arr[middle + 1]) {
                start = middle + 2;
            } else {
                end = middle;
            }
        }
        return arr[start];
    }
};

The provided C++ code aims to solve the problem of finding a single element in a sorted array where every other element appears twice. The solution employs a binary search algorithm to efficiently locate the non-repeating element. Follow the detailed breakdown of the code:

1. Initialize two pointers, start set to 0 and end set to the last index of the array.
2. Use a while loop to iterate until start is less than end.
3. Calculate the middle index using start and end to potentially halve the search space in each iteration.
4. Since the elements are in pairs, adjust the middle index to be even, ensuring it starts at the beginning of a pair.
5. Compare the element at the middle index with the next element:
   • If they are equal, it means the single element is beyond this point. Thus, move the start pointer to middle + 2.
   • If they are not equal, update the end pointer to middle.
6. After exiting the loop, the start pointer will point to the single element in the array.

The binary search approach ensures the algorithm runs in O(log n) time, making it very efficient for large arrays. The condition inside the while loop ensures that the search space is correctly narrowed down to the segment of the array containing the single element.

class Solution {
    public int findUnique(int[] elements) {
        int low = 0;
        int high = elements.length - 1;
        while (low < high) {
            int middle = low + (high - low) / 2;
            if (middle % 2 == 1) middle--;
            if (elements[middle] == elements[middle + 1]) {
                low = middle + 2;
            } else {
                high = middle;
            }
        }
        return elements[low];
    }
}

The provided Java solution is designed to identify a single element in a sorted array where every other element appears exactly twice. This algorithm is efficient, operating in logarithmic time complexity, O(log n), which is optimal for this type of search problem due to the use of a binary search pattern. Follow these steps to understand how the solution works:

1. Initialize two pointers, low at the beginning of the array and high at the end (elements.length - 1).
2. Enter a loop that continues as long as low is less than high. This loop ensures that as soon as low equals high, the single element has been found.
3. Calculate the middle of the current sub-array. This involves finding the average of low and high and adjusting it if it is an odd number (if (middle % 2 == 1) middle--;). This adjustment keeps the middle pointing to the start of a pair in the array.
4. Check if the element at the middle index is the same as the one next to it (elements[middle + 1]). If they are the same, it indicates that the single element is further in the array, so adjust low to skip to the next pair (middle + 2). If they are not the same, adjust high to focus on the current pair.
5. When the loop exits, return the element at the low index, which will be your single unpaired element.

This approach guarantees that the search space is halved in each iteration, making the algorithm significantly faster than a linear scan, especially for large arrays. Ensure the array is sorted and adheres to the stated conditions (all elements, except one, appear exactly twice) for the solution to work correctly.