Single Element in a Sorted Array

Problem Statement:

You are given a sorted array consisting of only integers where every element appears exactly twice, except for one element which appears exactly once. Return the single element that appears only once. Your solution must run in O(log n) time and O(1) space.

Example 1:

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

Example 2:

Input: nums = [3,3,7,7,10,11,11] Output: 10

Constraints:

• 1 <= nums.length <= 10^5
• 0 <= nums[i] <= 10^5

Solution:

class Solution {
    private boolean isSingleEncountered(int[] nums, int mid){
        //Observation:
        // Single element ke pehle humare pairs Even, Odd indices pe rehte
        // uske baad Odd, Even indices pe.
 
        //Implementation:
        //agar index even hai toh next index wala element bhi same hona 
        //chaiye to be a pair IFF single element is not encountered.
 
        if(mid % 2 == 0){
            //If it's true, iska matlab single element encounter ni hua hai,
            //hua hota toh Even and ODD wala order maintained rehta.
            if(nums[mid] == nums[mid + 1]){ 
                return false;
            } else{ //ho gaya encounter single element ka
                return true;
            }
        } else{
            if(nums[mid] == nums[mid - 1]){
                return false;
            } else{
                return true;
            }
        }
    }
    public int singleNonDuplicate(int[] nums) {
	    //Search space,i.e, single element kahan pe present ho sakta
        int left = 0;
        int right = nums.length - 1;
 
        while(left < right){
            int mid = left + (right - left)/2;
 
            if(isSingleEncountered(nums, mid)){
                right = mid;
            } else{
                left = mid + 1;
            }
        }
        return nums[left];
    }
}