Amazon
Microsoft
2020-05-12
540. Single Element in a Sorted Array
Question:
You are given a sorted array consisting of only integers where every element appears exactly twice, except for one element which appears exactly once. Find this single element that appears only once.
Example 1:
Input: [1,1,2,3,3,4,4,8,8]
Output: 2
Example 2:
Input: [3,3,7,7,10,11,11]
Output: 10
Note: Your solution should run in O(log n) time and O(1) space.
Solution:
Find the closest even number near middle, if nums[middle] != nums[middle + 1], it means the target value is on the left side. Otherwise, it will be on the right side.
class Solution {
public int singleNonDuplicate(int[] nums) {
int left = 0;
int right = nums.length - 1;
while (left < right) {
int middle = left + (right - left) / 2;
if (middle % 2 == 1) middle--;
if (nums[middle] == nums[middle + 1]) left = middle + 2;
else right = middle;
}
return nums[left];
}
}