Question : You are given a sorted array . In the array all elements appeared twice , and there is only one element which appears only once.Find the element which appears only once .

Input : arr[] = {1, 1, 3, 3, 4, 5, 5, 7, 7, 8, 8}
Output: 4

Brute Force :
We can simply traverse the array from left to right . Whenever we find that our current element isnot equal to next element we can just return the element i.e. arr[i]!=arr[i+1].
Pseudo Code :
for(i=0 ;i<=n-1;i+=2)
{ if(arr[i]!=arr[i+1]){
return arr[i];
}
}

Time Complexity : O(n)
Space Complexity : O(1)

Optimal Solution :
We can optimize the time complexity using binary search . We will try to apply binary search and try to find a break point such that to the left of it all the elements appears twice and from the right your single element starts appearing .In order to find this breakpoint we are just going to use a simple observation .

To get a understanding of the break point , take the example of input array :
arr[] = {1, 1, 3, 3, 4, 5, 5, 7, 7, 8, 8} ;
Now if we look at the indexes it will look like this :
arr[]={1 ,1 , 3, 3 ,4 ,5 ,5 , 7 , 7, 8 ,8}
index= 0 ,1 , 2, 3, 4, 5 ,6 , 7 , 8, 9 ,10

Now after index 4 ; if we see for the repetitive elements first element appears at odd index and second elements appear at even index , say for 5 , first is at index 5 and second 5 is at index 6 .
Before index 4 , if we see for the repetitive elements first element appears at even index and second elements appear at odd index .Take example of 1 , first is at index 0 and second is at index 1.

This observation is useful . We can use this and implement binary search in the array to find our answer.

Initially keep a low pointer at the zeroth index and keep a high pointer at the second last index and mid pointer at (low+high)/2 . Here we will be taking high at second last index instead of last beacuse of one corner case which is described below at point (A) .

Now you need to check left and right half of middle element. Now if your mid is odd index ,check your previous element ,if it is equal then you are currently at the left of single element .
arr[]={1 ,1 , 3, 3 ,4
index= 0 ,1 , 2, 3, 4
So you need to move to right , to do this , you have to do low=mid+1 ,
else , if your previous element isnot equal move to left by doing high=mid-1.

Now if your mid is even index ,check your next element ,if it is equal then you are currently at the right of single element .
arr[]={1 ,1 , 3, 3 ,4
index= 0 ,1 , 2, 3, 4
So you need to move to right , to do this , you have to do low=mid+1 ,
else , if your previous element isnot equal move to left by doing high=mid-1.

If you continue this approach , once low crosses high , low will contain the answer that is single element .

(A) : take an example of this array : arr :[ 1 1 2 2 4 4 5] .Here our single element occurs at the the end.Now we will start with low=0 and high=n-2 , and we get our answers when low crosses high and after that low contain the answer . Now in this kind of cases low will only cross high and have a valid index only if we take high=n-2.

Code :
C++
Function to find the single element :

int singleNonDuplicate(vector<int>& nums) {
 int low=0;     
int high=nums.size()-2;     
while(low<=high){         
int mid=(low+high)/2;         
if(mid%2==0){

 if(nums[mid+1]==nums[mid]){
         low=mid+1;}             
else            
 {  high=mid-1;  }

}
else{


if(nums[mid-1]==nums[mid])
 {  low=mid+1; }            
 else {   high=mid-1;}        

}
}
return nums[low];

}
Time Complexity : O(logn)
Space Complexity : O(1)