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.
与Leetcode Search in Rotated Sorted Array 类似。解题思路一致。只有重复数的差别。
当有重复数字，会存在A[mid] = A[end]的情况。此时右半序列A[mid-1 : end]可能是sorted，也可能并没有sorted，如下例子。
3 1 2 3 3 3 3
3 3 3 3 1 2 3
所以当A[mid] = A[end] != target时，无法排除一半的序列，而只能排除掉A[end]：
A[mid] = A[end] != target时：搜寻A[start : end-1]
正因为这个变化，在最坏情况下，算法的复杂度退化成了O(n)：
public class Solution { public boolean search(int[] nums, int target) { int left = 0, right = nums.length-1; int index = -1; while(left <= right){ int mid = left + (right - left)/2; if(nums[mid] == target) { index = mid; } if(nums[mid] < nums[right]) { //right half sorted if(target > nums[mid] && target <= nums[right]){ left = mid+1; }else{ right = mid-1; } }else if(nums[mid] > nums[right]){ //left half sorted if(target >= nums[left] && target < nums[mid]){ right = mid-1; }else { left = mid+1; } }else{ right--; } } return index != -1; } }
Reference:
1. http://bangbingsyb.blogspot.com/2014/11/leetcode-search-in-rotated-sorted-array.html
Leetcode Search in Rotated Sorted Array II
原文：http://www.cnblogs.com/anne-vista/p/4899753.html