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.
是medium。如果没有最后一句要求就是easy了。第一反应肯定是brute force， 因为就算brute force， time complexity 也就只有O(n),, 然而，这里需要O(logn). 一看到O(logn)， 第一反应就是binary search。这个也就给接下来解题指定了方向。
比较好理解的一种方法就是去掉mid和(mid -1 or mid +1)以后左右两边的section是不是even。
class Solution {
public int singleNonDuplicate(int[] nums) {
int left = 0, right = nums.length - 1;
while(left<right) {
int mid = left + (right - left)/2;
boolean rightHalfIsEven = (right - mid) % 2 == 0;
if(nums[mid] == nums[mid+1]) {
if(rightHalfIsEven) {
left = mid + 2;
} else {
right = mid - 1;
}
} else if(nums[mid] == nums[mid -1]){
if(rightHalfIsEven) {
right = mid - 2;
} else {
left = mid + 1;
}
} else {
return nums[mid];
}
}
return nums[left];
}
}
最后注意一下corner case，就是最后返回nums[left]那边。
我看有人解释怎么判断l<r还是l<=right:
Easy heuristic:
if you discard mid for the next iteration (i.e. l = mid+1 or r = mid-1) then use while (l <= r).
if you keep mid for the next iteration (i.e. l = mid or r = mid) then use while (l < r)
还有就是：
if you are returning from inside the loop, use left <= right
if you are reducing the search space, use left < right and finally return a[left]
可以作为参考。但是对我们这个solution都不适用哈哈哈哈。所以还是以具体问题具体分析，多用corner case test比较好。
