Since the array is sorted and every element appears exactly twice except for one, the unique element must disrupt the pairing pattern. Normally, pairs start at even indices (0, 2, 4, …). If we find the first index where this pattern breaks, the single element is at or just before that position. Binary search allows us to efficiently find this point by checking the relationship between the current index and its neighbor.
classSolution {
public:int singleNonDuplicate(vector<int>& nums) {
int left =0, right = nums.size() -1;
while (left < right) {
int mid = left + (right - left) /2;
if (mid %2==1) mid--;
if (nums[mid] == nums[mid +1]) left = mid +2;
else right = mid;
}
return nums[left];
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
funcsingleNonDuplicate(nums []int) int {
left, right:=0, len(nums)-1forleft < right {
mid:=left+ (right-left)/2ifmid%2==1 {
mid-- }
ifnums[mid] ==nums[mid+1] {
left = mid+2 } else {
right = mid }
}
returnnums[left]
}
1
2
3
4
5
6
7
8
9
10
11
12
classSolution {
publicintsingleNonDuplicate(int[] nums) {
int left = 0, right = nums.length- 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (mid % 2 == 1) mid--;
if (nums[mid]== nums[mid + 1]) left = mid + 2;
else right = mid;
}
return nums[left];
}
}
1
2
3
4
5
6
7
8
9
10
11
12
classSolution:
defsingleNonDuplicate(self, nums: list[int]) -> int:
left, right =0, len(nums) -1while left < right:
mid = (left + right) //2if mid %2==1:
mid -=1if nums[mid] == nums[mid +1]:
left = mid +2else:
right = mid
return nums[left]
1
2
3
4
5
6
7
8
9
10
11
12
13
classSolution {
funsingleNonDuplicate(nums: IntArray): Int {
var left = 0var right = nums.size - 1while (left < right) {
var mid = left + (right - left) / 2if (mid % 2==1) mid--if (nums[mid] == nums[mid + 1]) left = mid + 2else right = mid
}
return nums[left]
}
}
1
2
3
4
5
6
7
8
9
10
functionsingleNonDuplicate(nums: number[]):number {
letleft=0, right=nums.length-1;
while (left<right) {
letmid= Math.floor((left+right) /2);
if (mid%2===1) mid--;
if (nums[mid] ===nums[mid+1]) left=mid+2;
elseright=mid;
}
returnnums[left];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
impl Solution {
pubfnsingle_non_duplicate(nums: Vec<i32>) -> i32 {
let (mut left, mut right) = (0, nums.len() -1);
while left < right {
letmut mid = (left + right) /2;
if mid %2==1 { mid -=1; }
if nums[mid] == nums[mid +1] {
left = mid +2;
} else {
right = mid;
}
}
nums[left]
}
}