Search in Rotated Sorted Array.png

===================== 解題思路 =====================

題目要求要 log(n) 解 所以不能先 sort 依舊使用二分法 在拿到 mid 數值以後 先檢查是否為 target 若不是則跟 vector 的頭一個數值比較 共有兩種情況：

1. 如果 A[mid] > A[left] 則表示 A[left] ~ A[mid] 之間是原本的沒經過 rotate 的部分 是一段 sort 好的值 優先確認 target 是否在其中 如果在其中即可設定 right = mid 縮小範圍 不在其中就設定 left = mid 來往另一邊縮小
2. 另一種情形 A[mid] < A[left] 則相反先檢查 A[mid] ~ A[end] 的區段 因為這時候這一段是 sort 好的沒有被 rotate 的部分 所以檢查 target 是否在其中 有的話設定 left = mid 反之 right = mid

最後在檢查 left 跟 right 是否有出現 target 沒有則返回 -1

===================== C++ code ====================

<pre><code>
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) {
    // write your code here
    if(A.size() == 0) return -1;
    int left = 0, right = A.size() -1;
    while(left + 1 < right)
    {
        int mid = left + (right - left) / 2;
        if(A[mid] == target) return mid;
        if(A[mid] >= A[0])
        {
            if(A[0] <= target && target <= A[mid]) right = mid;
            else left = mid;
        }
        else
        {
            if(A[mid] <= target && target <= A[A.size() - 1]) left = mid;
            else right = mid;
        }
    }
    if(A[left] == target) return left;
    if(A[right] == target) return right;
    return -1;
}

};
<code><pre>