Search in Rotated Sorted Array.png
===================== 解題思路 =====================
題目要求要 log(n) 解 所以不能先 sort 依舊使用二分法 在拿到 mid 數值以後 先檢查是否為 target 若不是則跟 vector 的頭一個數值比較 共有兩種情況：
- 如果 A[mid] > A[left] 則表示 A[left] ~ A[mid] 之間是原本的沒經過 rotate 的部分 是一段 sort 好的值 優先確認 target 是否在其中 如果在其中即可設定 right = mid 縮小範圍 不在其中就設定 left = mid 來往另一邊縮小
- 另一種情形 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>
