540. Single Element in a Sorted Array
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:
Example 2:
Constraints:
- 1 < = n u m s . l e n g t h < = 1 0 5 1 <= nums.length <= 10^5 1<=nums.length<=105
- 0 < = n u m s [ i ] < = 1 0 5 0 <= nums[i] <= 10^5 0<=nums[i]<=105
From: LeetCode
Link: 540. Single Element in a Sorted Array
Solution:
Ideas:
1. Pairs Observation: In a perfectly paired array where each element appears exactly twice, if you pick any even index (0, 2, 4,…), the next index should have the same value if there’s no single element disrupting the pairing.
2. Detecting the Single Element Influence: When the single element is introduced, it disrupts these pairings. Specifically, the first occurrence of every element in a disrupted array will start appearing at an even index and end at an odd index (before the single element appears).
3. Binary Search Strategy:
- Check the middle index of the array.
- If the middle index is even, then check the next element. If they are the same, it means the single element is ahead; otherwise, it’s behind.
- If the middle index is odd, then check the previous element. If they are the same, it means the single element is ahead; otherwise, it’s behind.
- Adjust the search boundaries accordingly until you find the single element.
Code:
int singleNonDuplicate(int* nums, int numsSize) {
int low = 0, high = numsSize - 1;
while (low < high) {
int mid = low + (high - low) / 2;
// Ensure mid is even. If mid is odd, decrease by 1 to make it even.
if (mid % 2 == 1) mid--;
// Check pairs: nums[mid] should be the same as nums[mid + 1]
if (nums[mid] == nums[mid + 1]) {
// If they are the same, move to the right half
low = mid + 2;
} else {
// If not the same, move to the left half
high = mid;
}
}
// Low should point to the single element
return nums[low];
}