刷题（8）leetcode 81 -- binary searc
leetcode 81. Search in Rotated Sorted Array II
这是一道medium题，在做这道题之前，如果弄明白了leetcode 33. Search in Rotated Sorted Array，那么做这道题目会简单一些。
33. Search in Rotated Sorted Array 也是medium题。题目是说一个array是增序排列，但是呢以一个pivot做了rotate，pivot在哪个位置不定，求给定的target是否在这个rotated array中存在。e.g, Input:nums = [4,5,6,7,0,1,2], target = 0 Output:4(index)
my solution:
class Solution {
public int search(int[] nums, int target) {
int start =0, end = nums.length - 1;
while(start<=end) {
int mid = start + (end - start) / 2;
if(nums[mid] == target) {
return mid;
} else if(nums[mid] < nums[start]) {
// we can only ensure the right part is sorted
if(target > nums[mid] && target <= nums[end]) {
start = mid + 1;
} else {
end = mid - 1;
}
} else {
// we can only ensure the left part is sorted
if(target<nums[mid] && target >= nums[start]) {
end = mid -1;
} else {
start = mid + 1;
}
}
}
return -1;
}
}
做完33，我们再看81， 81是说这个rotated array里面的数字可以重复。
如果可以重复，跟33的区别就是，当mid的值和start或者end相等的时候，你不知道应该接下来取哪一半的值，因为可能mid在pivot左边，也可能在右边。为了避免这种情况，我们把start和end的两边重复的值去掉，这样可以保证mid的值至少不会与start或者end相同。这样就能知道接下来取哪一边的值。
class Solution {
public boolean search(int[] nums, int target) {
int start =0, end = nums.length - 1;
while(start<=end) {
while (start < end && nums[start] == nums[start + 1])
++start;
while (start < end && nums[end] == nums[end - 1])
--end;
int mid = start + (end - start) / 2;
if(nums[mid] == target) {
return true;
} else if(nums[mid] < nums[start]) {
if(target > nums[mid] && target <= nums[end]) {
start = mid + 1;
} else {
end = mid - 1;
}
} else {
if(target<nums[mid] && target >= nums[start]) {
end = mid -1;
} else {
start = mid + 1;
}
}
}
return false;
}
}
这个time complexity: O(N) worst case, O(logN) best case, where N is the length of the input array.
Worst case: This happens when all the elements are the same and we search for some different element. At each step, we will only be able to reduce the search space by 1 since arr[mid] equals arr[start] and it's not possible to decide the relative position of target from arr[mid]. Example: [1, 1, 1, 1, 1, 1, 1], target = 2.
Best case: This happens when all the elements are distinct. At each step, we will be able to divide our search space into half just like a normal binary search.
space complexityO(1)
这道题还有一个follow up：
This problem is similar to Search in Rotated Sorted Array, but nums may contain duplicates. Would this affect the runtime complexity? How and why?
从刚刚的分析就可以看出，当有重复值时，会让我么不能用binary search，所以这时候就多了一个最坏情况和一个最好情况。最好情况就是跟33一样。
