540. Single Element in a Sorted Array
1. Description
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.
2. Example
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
3. Constraints
- 1 <= nums.length <= $10^5$
- 0 <= nums[i] <= $10^5$
4. Solutions
Binary Search
n = nums.size()
Time complexity: O(logn)
Space complexity: O(1)
class Solution {
private:
bool check(const vector<int> &nums, int index) {
// before the sigle element, even index element and even + 1 index element are equal
// after it, odd index element and odd + 1 index element are equal
return ((index & 1) == 1 && nums[index] == nums[index - 1]) ||
((index & 1) == 0 && index + 1 < nums.size() && nums[index] == nums[index + 1]);
}
public:
int singleNonDuplicate(const vector<int> &nums) {
int result = nums[0];
for (int left = 0, right = nums.size(); left < right;) {
int mid = (left + right) / 2;
check(nums, mid) ? left = mid + 1, result = nums[mid + 1] : right = mid;
}
return result;
}
};