【题目】
Follow up for "Search in Rotated Sorted Array":What ifduplicatesare allowed?
Would this affect the run-time complexity? How and why?
Write a function to determine if a given target is in the array.
【解析】
相比Search in Rotated Sorted Array，，在递归时需要先去重，再迭代（递归）。
【C++代码】
class Solution {public:bool search(int A[], int n, int key) {if (n<=0) return false;if (n==1){return (A[0]==key) ? true : false;}int low=0, high=n-1;while( low<=high ){if (A[low] < A[high] && ( key < A[low] || key > A[high]) ) {return false;}//if dupilicates, them binary search the duplicationwhile (low < high && A[low]==A[high]){low++;}int mid = low + (high-low)/2;if (A[mid] == key) return true;//the target in non-rotated arrayif (A[low] < A[mid] && key >= A[low] && key< A[mid]){high = mid – 1;continue;}//the target in non-rotated arrayif (A[mid] < A[high] && key > A[mid] && key <= A[high] ){low = mid + 1;continue;}//the target in rotated arrayif (A[low] > A[mid] ){high = mid – 1;continue;}//the target in rotated arrayif (A[mid] > A[high] ){low = mid + 1;continue;}//reach here means nothing found.low++;}return false;}};
【简洁Java版】
public class Solution {public boolean search(int[] A, int target) {int l = 0;int r = A.length – 1;while (l <= r) {while (l < r && A[l] == A[r]) l++;int mid = (l + r) / 2;if (target == A[mid]) return true;if (A[l] <= A[r]) {if (target < A[mid]) r = mid – 1;else l = mid + 1;} else if (A[l] <= A[mid]) {if (target < A[l] || target > A[mid]) l = mid + 1;else r = mid – 1;} else {if (target < A[mid] || target > A[r]) r = mid – 1;else l = mid + 1;}}return false;}}
蝙蝠黑暗中闯荡，树木默默的成长，蝴蝶破蛹后飞翔，
