Search in Rotated Sorted Array II 63
Question
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.
Example
Given [1, 1, 0, 1, 1, 1] and target = 0, return true.
Given [1, 1, 1, 1, 1, 1] and target = 0, return false.
Solution
这道题是有重复元素的情况下对rotated sorted array进行搜索。
一种做法是进行顺序搜索,这样复杂度是O(n)。
另一种做法是进行二分搜索,但是因为有重复元素(特别是重复元素有可能被分在前后区间),此时对于nums[mid] == nums[left]情况不能像之前那样合并在nums[left] < nums[mid]或者nums[left] > nums[mid]之中进行讨论,必须进行单独讨论,因为nums[mid] == nums[left]有可能是因为mid==left,但也有可能是因为nums[mid]和nums[left]是重复元素,如果是后面这种情况则mid有可能其实是落在后半区,这时能确定的只是nums[left]一定不等于target,其他情况都是不确定的,因此最保险的方法是只将left向右移动一步,即left++。这种情况下,如果数组大部分是重复元素,则复杂度接近O(n),但是如果重复元素较少,则时间复杂度接近O(logn)。
代码如下:
public class Solution {
/**
* param A : an integer ratated sorted array and duplicates are allowed
* param target : an integer to be search
* return : a boolean
*/
public boolean search(int[] A, int target) {
// write your code here
int[] nums = A;
if(nums == null || nums.length == 0){
return false;
}
int left = 0;
int right = nums.length - 1;
while(left + 1 < right){
int mid = left + (right - left) / 2;
if(nums[mid] == target){
return true;
}else if(nums[left] < nums[mid]){
if(nums[left] <= target && target <= nums[mid]){
right = mid;
}else{
left = mid;
}
}else if(nums[left] > nums[mid]){
if(nums[mid] <= target && target <= nums[right]){
left = mid;
}else{
right = mid;
}
}else if(nums[left] == nums[mid]){
//这里是关键,如果有重复元素,只将left向right移动一位,肯定不会有问题
left++;
}
}
if(nums[left] == target){
return true;
}else if(nums[right] == target){
return true;
}
return false;
}
}