Follow

# .css-ecb9sr{display:-webkit-box;display:-webkit-flex;display:-ms-flexbox;display:flex;-webkit-flex-direction:row;-ms-flex-direction:row;flex-direction:row;-webkit-align-items:center;-webkit-box-align:center;-ms-flex-align:center;align-items:center;width:16rem;}  Follow # 540. Single Element in a Sorted Array

## An example of using the binary search algorithm

Nhut Nguyen
·Jan 23, 2023·

### 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 1: Bruteforce

#### Code

``````#include <vector>
#include <iostream>
using namespace std;
int singleNonDuplicate(vector<int>& nums) {
for (int i = 0; i < nums.size() - 1; i += 2) {
if (nums[i] != nums[i + 1]) {
return nums[i];
}
}
return nums;
}
int  main() {
vector<int> nums{1,1,2,3,3,4,4,8,8};
cout << singleNonDuplicate(nums) << endl;
nums = {3,3,7,7,10,11,11};
cout << singleNonDuplicate(nums) << endl;
nums = {3};
cout << singleNonDuplicate(nums) << endl;
}
``````
``````Output:
2
10
3
``````

#### Complexity

• Runtime `O(n/2)`, where `n = nums.length`.

• Memory `O(1)`.

Since `nums` is sorted, you can perform a binary search on it.

Let us divide `nums` into two halves.

If the single element belongs to the right half, all elements of the left half satisfy `nums[2*i] == nums[2*i + 1]`.

Conversely, if the single element belongs to the left half, that condition is violated at the middle element of `nums` (the middle one with an even index).

#### Example 1

For `nums = [1,1,2,3,3,4,4,8,8]`:

• The middle element with even index is `nums = 3`. It is not equal to `nums[4 + 1] = 4`. So the single element must be somewhere in the left half `[1,1,2,3,3]`.

• The middle element of `nums = [1,1,2,3,3]` with even index is `nums = 2`, which is not equal to `nums[2 + 1] = 3`. So the single element must be somewhere in the left half `[1,1,2]`.

• The middle element of `nums = [1,1,2]` with even index is `nums = 1 == nums[0 + 1]`. So the single element must be somewhere in the right half ``.

• `nums = ` contains only one element. So `2` is the result.

#### Code

``````#include <vector>
#include <iostream>
using namespace std;
int singleNonDuplicate(vector<int>& nums) {
int left = 0;
int right = nums.size() - 1;
while (left < right) {
int mid = (right + left)/4 * 2; // to make sure mid is even
if (nums[mid] != nums[mid + 1]) {
right = mid;
} else {
left = mid + 2;
}
}
return nums[right];
}
int  main() {
vector<int> nums{1,1,2,3,3,4,4,8,8};
cout << singleNonDuplicate(nums) << endl;
nums = {3,3,7,7,10,11,11};
cout << singleNonDuplicate(nums) << endl;
nums = {3};
cout << singleNonDuplicate(nums) << endl;
}
``````
``````Output:
2
10
3
``````

#### Complexity

• Runtime `O(logn)`, where `n = nums.length`.

• Memory `O(1)`.

### Reference

Thanks for reading. Feel free to share your thought about my content and check out my FREE book “10 Classic Coding Challenges”.