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.
I remember maybe it's a xor problem? nope. the xor need o(n). So we need to use binary search. I have done it before. So let me just see my code.
we have to perform binary search in the array. But how to move left or right? If each number appears twice, then it will be 11 22 33 44
and for the odd length n. down(n/2) -> means the middle, let me give an example
01 23 45 6 => single one in the right for 3
01 2 34 56 => single one in the left for 3
So, we can determine which one is the duplicate to decide to move to the next or right? let me try.
Also, we need to return the value.
And, for the final binary search iteration, we reach right and right + 1 as left. We still have to determine which one is single by their adjacent value and determine whether we reach the first and last index. Because it will do not have left or right value when we in the start and end.