# Search in Rotated Sorted Array II ### Source - leetcode: [Search in Rotated Sorted Array II | LeetCode OJ](https://leetcode.com/problems/search-in-rotated-sorted-array-ii/) - lintcode: [(63) Search in Rotated Sorted Array II](http://www.lintcode.com/en/problem/search-in-rotated-sorted-array-ii/) ### Problem 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. ### 題解 仔細分析此題和之前一題的不同之處，前一題我們利用`A[start] < A[mid]`這一關鍵信息，而在此題中由于有重復元素的存在，在`A[start] == A[mid]`時無法確定有序數組，此時只能依次遞增start/遞減end以縮小搜索范圍，時間復雜度最差變為O(n)。 ### C++ ~~~ class Solution { /** * param A : an integer ratated sorted array and duplicates are allowed * param target : an integer to be search * return : a boolean */ public: bool search(vector<int> &A, int target) { if (A.empty()) { return false; } vector<int>::size_type start = 0; vector<int>::size_type end = A.size() - 1; vector<int>::size_type mid; while (start + 1 < end) { mid = start + (end - start) / 2; if (target == A[mid]) { return true; } if (A[start] < A[mid]) { // situation 1, numbers between start and mid are sorted if (A[start] <= target && target < A[mid]) { end = mid; } else { start = mid; } } else if (A[start] > A[mid]) { // situation 2, numbers between mid and end are sorted if (A[mid] < target && target <= A[end]) { start = mid; } else { end = mid; } } else { // increment start ++start; } } if (A[start] == target || A[end] == target) { return true; } return false; } }; ~~~ ### Java ~~~ 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) { if (A == null || A.length == 0) return false; int lb = 0, ub = A.length - 1; while (lb + 1 < ub) { int mid = lb + (ub - lb) / 2; if (A[mid] == target) return true; if (A[mid] > A[lb]) { // case1: numbers between lb and mid are sorted if (A[lb] <= target && target <= A[mid]) { ub = mid; } else { lb = mid; } } else if (A[mid] < A[lb]) { // case2: numbers between mid and ub are sorted if (A[mid] <= target && target <= A[ub]) { lb = mid; } else { ub = mid; } } else { // case3: A[mid] == target lb++; } } if (target == A[lb] || target == A[ub]) { return true; } return false; } } ~~~ ### 源碼分析 在`A[start] == A[mid]`時遞增start序號即可。 ### 復雜度分析 最差情況下 O(n)O(n)O(n), 平均情況下 O(logn)O(\log n)O(logn).