Follow up for "Search in Rotated Sorted Array":
What if duplicates are allowed? Would this affect the run-time complexity? How and why? Write a function to determine if a given target is in the array.
解决方法就是对于A[mid]==A[left]和A[mid]==A[right]单独处理。
public class Solution {
public boolean search(int[] nums, int target) {
if(nums==null || nums.length==0){
return false;
}
int left=0;
int right=nums.length-1;
while(left<=right){
int mid=left+(right-left)/2;
if(target<nums[mid]){
if(nums[mid]< nums[right]){// right side is sorted
right=mid-1;
}
else if(nums[mid] == nums[right]){//can't tell right is sorted or not, move pointer
right--;
}
else {//left side is sorted
if(target<nums[left]){
left=mid+1;
}
else{
right=mid-1;
}
}
}
else if(target>nums[mid]){
if(nums[mid] > nums[left]){//left is sorted
left=mid+1;
}
else if(nums[mid]== nums[left]){// cann't tell left side is sorted or not, move pointer
left++;
}
else{//right is sorted
if(target>nums[right]){
right=mid-1;
}
else{
left=mid+1;
}
}
}
else{
return true;
}
}
return false;
}
}