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.
33. Search in Rotated Sorted Array 的拓展，数组中允许出现重复数字，这个也会影响我们选择哪半边继续搜索，之前判断左右部分是否有序的方法就失效了，因为可能有这种58555情况，虽然起点小于等于中间，但不代表右边就不是有序的，因为中点也小于等于终点，所有右边也是有序的。所以，如果遇到这种中点和两边相同的情况，我们两边都要搜索。
Java：
public class Solution {
public boolean search(int[] nums, int target) {
return helper(nums, 0, nums.length - 1, target);
}
public boolean helper(int[] nums, int min, int max, int target){
int mid = min + (max - min) / 2;
// 不符合min <= max则返回假
if(min > max){
return false;
}
if(nums[mid] == target){
return true;
}
boolean left = false, right = false;
// 如果左边是有序的
if(nums[min] <= nums[mid]){
// 看目标是否在左边有序数列中
if(nums[min] <= target && target < nums[mid]){
left = helper(nums, min, mid - 1, target);
} else {
left = helper(nums, mid + 1, max, target);
}
}
// 如果右边也是有序的
if(nums[mid] <= nums[max]){
// 看目标是否在右边有序数列中
if(nums[mid] < target && target <= nums[max]){
right = helper(nums, mid + 1, max, target);
} else {
right = helper(nums, min, mid - 1, target);
}
}
// 左右两边有一个包含目标就返回真
return left || right;
}
}
Python：
class Solution(object):
def search(self, nums, target):
left, right = 0, len(nums) - 1 while left <= right:
mid = left + (right - left) / 2 if nums[mid] == target:
return True
elif nums[mid] == nums[left]:
left += 1
elif (nums[mid] > nums[left] and nums[left] <= target < nums[mid]) or \
(nums[mid] < nums[left] and not (nums[mid] < target <= nums[right])):
right = mid - 1
else:
left = mid + 1 return False
类似题目：
[LeetCode] 33. Search in Rotated Sorted Array 在旋转有序数组中搜索
All LeetCode Questions List 题目汇总