# Search in Rotated Sorted Array ### Source - leetcode: [Search in Rotated Sorted Array | LeetCode OJ](https://leetcode.com/problems/search-in-rotated-sorted-array/) - lintcode: [(62) Search in Rotated Sorted Array](http://www.lintcode.com/en/problem/search-in-rotated-sorted-array/) ### Problem Suppose a sorted array 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`). You are given a target value to search. If found in the array return itsindex, otherwise return -1. You may assume no duplicate exists in the array. #### Example For `[4, 5, 1, 2, 3]` and `target=1`, return `2`. For `[4, 5, 1, 2, 3]` and `target=0`, return `-1`. #### Challenge O(logN) time ### 題解 - 找到有序數組 對于旋轉數組的分析可使用畫圖的方法，如下圖所示，升序數組經旋轉后可能為如下兩種形式。  對于有序數組，使用二分搜索比較方便。分析題中的數組特點，旋轉后初看是亂序數組，但仔細一看其實里面是存在兩段有序數組的。剛開始做這道題時可能會去比較`target`和`A[mid]`, 但分析起來異常復雜。**該題較為巧妙的地方在于如何找出旋轉數組中的局部有序數組，并使用二分搜索解之。**結合實際數組在紙上分析較為方便。 ### C++ ~~~ /** * 本代碼fork自 * http://www.jiuzhang.com/solutions/search-in-rotated-sorted-array/ */ class Solution { /** * param A : an integer ratated sorted array * param target : an integer to be searched * return : an integer */ public: int search(vector<int> &A, int target) { if (A.empty()) { return -1; } 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 mid; } 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 { // situation 2, numbers between mid and end are sorted if (A[mid] < target && target <= A[end]) { start = mid; } else { end = mid; } } } if (A[start] == target) { return start; } if (A[end] == target) { return end; } return -1; } }; ~~~ ### Java ~~~ public class Solution { /** *@param A : an integer rotated sorted array *@param target : an integer to be searched *return : an integer */ public int search(int[] A, int target) { if (A == null || A.length == 0) return -1; int lb = 0, ub = A.length - 1; while (lb + 1 < ub) { int mid = lb + (ub - lb) / 2; if (A[mid] == target) return mid; 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 { // case2: numbers between mid and ub are sorted if (A[mid] <= target && target <= A[ub]) { lb = mid; } else { ub = mid; } } } if (A[lb] == target) { return lb; } else if (A[ub] == target) { return ub; } return -1; } } ~~~ ### 源碼分析 1. 若`target == A[mid]`，索引找到，直接返回 1. 尋找局部有序數組，分析`A[mid]`和兩段有序的數組特點，由于旋轉后前面有序數組最小值都比后面有序數組最大值大。故若`A[start] < A[mid]`成立，則start與mid間的元素必有序（要么是前一段有序數組，要么是后一段有序數組，還有可能是未旋轉數組）。 1. 接著在有序數組`A[start]~A[mid]`間進行二分搜索，但能在`A[start]~A[mid]`間搜索的前提是`A[start] <= target <= A[mid]`。 1. 接著在有序數組`A[mid]~A[end]`間進行二分搜索，注意前提條件。 1. 搜索完畢時索引若不是mid或者未滿足while循環條件，則測試A[start]或者A[end]是否滿足條件。 1. 最后若未找到滿足條件的索引，則返回-1. ### 復雜度分析 分兩段二分，時間復雜度仍近似為 O(logn)O(\log n)O(logn).