Single Element in a Sorted Array

This problem is taken from Leetcode and is as follows:

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.

Example 1:

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

Solving it in O(N) time was straightforward using XOR — dupes become zero while the single element is the result.
The code is :

class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        int res = 0;
        for(int i =0; i < nums.size(); i++){
            res = res ^ nums[i];
        }
        return res;
    }
};

The O(log n)approach was interesting. I had to exploit the fact that the array is already sorted, so using binary search was the intuition.

However, how should I reduce the size of the array? How do I decide whether I should opt for the left side of the array or the right side?

We already know that all the other elements are paired, so there has to be some sort of even-odd logic. Writing down a couple of test cases and analyzing them helped me arrive at the following idea — Find mid as usual in the binary search.

1. If my single element is on the left, and my mid is even, then arr[mid + 1] = arr[mid].
2. If my single element is on the left, and my mid is odd, then arr[mid — 1] = arr[mid].
3. If my single element is on the right, and my mid is even, then arr[mid — 1] = arr[mid].
4. If my single element is on the right, and my mid is odd, then arr[mid + 1] = arr[mid].

If all 4 cases are not satisfied, then it simply means that our single element is at the mid itself. RETURN IT!

The following is the not so optimized code that explains the overall thought process directly:

class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        if(nums.size() == 1)
            return  nums[0];
        int n = nums.size();
        int left = 0, right = nums.size() - 1;
        
        while(left <= right){
            int mid = left + (int)(right - left)/2;
            if(mid%2 == 0){
                if(mid + 1 < n && nums[mid] == nums[mid + 1])
                    left = mid + 2;
                else if(mid - 1 >= 0 && nums[mid] == nums[mid - 1])
                    right = mid - 2;
                else
                    return nums[mid];
            }
            if(mid%2 == 1){
                if(mid - 1 >= 0 && nums[mid] == nums[mid - 1])
                    left = mid + 1;
                else if(mid + 1 < n  && nums[mid] == nums[mid + 1])
                    right = mid - 1;
                else
                    return nums[mid];      
            }       
        }

         return nums[left];

    }
};

Of course, you could shrink the code by eliminating or combining a few conditionals together as:

class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        if(nums.size() == 1)
            return  nums[0];
        int n = nums.size();
        int left = 0, right = nums.size() - 1;
        
        while(left < right){
            int mid = left + (int)((right - left)/2);
            if(nums[mid] == nums[mid + 1] && mid%2 == 0)|| (nums[mid] == nums[mid - 1] && mid%2 == 1))
            left = mid + 1;
            else
            right = mid;     
        }
         return nums[left];
    }
};