Table of contents
Given problem
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
Using XOR bitwise operator
When reading the problem statement, the property of elements is that each element appears twice. To take advantage of this property, we can use XOR bitwise operator for all elements. Just because applying two same elements with XOR operator will be 0.
To understand why we have this property, we need to look at the formulation:
 1 + 1 = 0
 0 + 0 = 0
 0 + 1 = 1
 1 + 0 = 1
For example: 3 = 1100 => 1100 + 1100 = 0000
To know more about the bitwise operations, we can look at the following article Bit manipulation.
Below is our source code:
class Solution {
public int singleNonDuplicate(int[] nums) {
int singleNum = 0;
for (int i : nums) {
singleNum ^= i;
}
return singleNum;
}
}
The complexity of this solution is:
 Time complexity:
O(n)
.  Space complexity:
O(1)
.
Using Binary Search algorithm

Analysis
Due to the sorted array, Binary Search can be applied in this case. We will choose the third invariant of Binary Search.

Our requirement is to find the elementâ€™s value that is repeated one time.
So we need to seek the conditions that relates to
mid
pointer in Binary Search algorithm.Below are the two cases that our value is satisfied the conditions of
mid
pointer.
The
mid
will be at the middle of the array.In this case, the element with value
10
is compared with its adjacent elements. So our result will be:int left = 0; int right = nums.length; ... int mid = left + (right  left) / 2; if (nums[mid] != nums[mid  1] && nums[mid] != nums[mid + 1]) { return nums[mid]; }

But we have another edge case. How about the element with value
10
sit at the end of the array?The
mid + 1
will lead to the NullPointerException. So we will have the below segment code:if (nums[mid] != nums[mid  1] && mid + 1 == nums.length) { return nums[mid]; }
Why do we have these conditions?
Each element will be repeated twice. The
left
pointer always point to the last element that satisfies this condition. When themid
points to last element of the array, it means that the remaining elements satisfied this condition.Therefore, the element at the
mid
position will be need to check.


Which condition will we move the
right
,left
pointers?Because the characteristic of this problem is that each element will be repeated twice. So it affects to the odd/even index of each element in the array.

If
mid
points to the odd index, we only need to compare the elements atmid
andmid  1
positions.
Case 1:

Case 2:
So we have:
int mid = left + (right  left) / 2; if (mid %2 != 0 && nums[mid] == nums[mid  1]) { left = mid; } else { right = mid; }


If
mid
points to the even index, we only need to compare the elements atmid
andmid + 1
positions.
Case 1:

Case 2:
So we have:
int mid = left + (right  left) / 2; if (mid %2 == 0 && nums[mid] == nums[mid + 1]) { left = mid; } else { right = mid; }




Solution
class Solution { public int singleNonDuplicate(int[] nums) { int left = 0; int right = nums.length; while (left + 1 < right) { int mid = left + (right  left) / 2; if (nums[mid] != nums[mid  1] && (mid + 1 == nums.length  nums[mid] != nums[mid + 1])) { return nums[mid]; } else if ((mid % 2 == 0 && nums[mid] == nums[mid + 1])  (mid % 2 != 0 && nums[mid] == nums[mid  1])) { left = mid; } else { right = mid; } } return nums[left]; } }
The complexity of this solution is:
 Time complexity:
O(logn)
.  Space complexity:
O(1)
.
 Time complexity:
Wrapping up
Refer: