540. Single Element in a Sorted Array (Solution || Leetcode medium || Java)

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 <= 105
• 0 <= nums[i] <= 105

SOLUTION:

class Solution {
public int singleNonDuplicate(int[] nums) {
int start = 0;//Determining range for binary search
int end = nums.length — 1;

while(start <= end){//applying binary search

//As the numbers are occuring exactly two times, so if the number is not equal to its next number then that number is our answer
if(start < nums.length — 2 && nums[start] == nums[start+1]){
start += 2;
}else{
return nums[start];
}
//if the number from end is not equal to the number just before it that number is our answer
if(end > 1 && nums[end] == nums[end — 1]){
end -= 2;
}else{
return nums[end];
}
}

return -1;
}
}

TIME COMPLEXITY :- O(log(n))

SPACE COMPLEXITY :- O(1)

Thank you for reading. If you have any queries, please let me know in the comment section, I will surely be responsive toward that.