description:
Follow up for "Search in Rotated Sorted Array":
What if duplicates are allowed?Would this affect the run-time complexity? How and why?
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
Write a function to determine if a given target is in the array.
The array may contain duplicates.
Thoughts:
1.按照写rotated sorteg array时的思路，我写这个问题的时候，在重新设置low和high的时候，跳过了和middle一样的重复部分。另外要注意的一个点就是当nums[low]和nums[high]相等的时候我们要重新设置low和high
public boolean search(int[] nums, int target){
int low = 0;
int high = nums.length-1;
if(nums[high] == nums[low]&&nums.length>2){
for(int i = high-1;i>=low;i--){
if(nums[i] == nums[high]){
high--;
}
}
}
while(low <= high){
int middle = (low+high)/2;
if(nums[middle] == target){
return true;
}else if(nums[middle] >=nums[low]){
if(target>=nums[low] && target<nums[middle]){
for(int i = middle-1;i>=low;i--){
if(nums[i] == nums[middle]){
middle--;
}else{
break;
}
}
high = middle -1;
}else{
for(int i = middle+1;i<=high;i++){
if(nums[i] == nums[middle]){
middle++;
}else{
break;
}
}
low = middle + 1;
}
}else{
if(target>nums[middle]&&target<=nums[high]){
for(int i =middle+1;i<=high;i++){
if(nums[i] == nums[middle]){
middle++;
}else{
break;
}
}
low = middle +1;
}else{
for(int i = middle-1;i>=low;i--){
if(nums[i] == nums[middle]){
middle--;
}else{
break;
}
}
high = middle - 1;
}
}
}
return false;
}
2.前面的解法，思路是清晰的过程是麻烦的，需要加很多的判断条件，为了避免这个问题，我们不讲middle和low进行比较，而是让它和high进行比较，这样就能够避免之前的nums[low]和nums[high]相等的情况，所带来的麻烦。
public boolean search2(int[] nums, int target){
if(nums.length == 0){
return false;
}
int low = 0;
int high = nums.length - 1;
while(low < high){
int middle = (low +high)/2;
if(nums[middle] == target){
return true;
}else{
if(nums[middle] < nums[high]){
if(target > nums[middle] && target <= nums[high]){
low = middle + 1;
}else{
high = middle - 1;
}
}else if(nums[middle] > nums[high]){
if(target >= nums[low] & target < nums[middle]){
high = middle -1;
}else{
low = middle +1;
}
}else{
high--;
}
}
}
return nums[low]==target;
}