33. Search in Rotated Sorted Array
1.問題
假設有個依升冪排序的array, 在某個pivot旋轉, 給予一個target, 找出他在array中的位置, 若找不到則回傳-1

2.想法
這題必須使用Binary search來做, 但是rotated list不是sorted list
3.程式碼
class Solution {
public:
int search(vector<int>& nums, int target) {
int n = nums.size();
return searchRotatedSortedArray(nums, 0, n-1, target);
}
private:
int searchRotatedSortedArray(vector<int>& A, int start, int end, int target) {
if(start > end) {
return -1;
}
int mid = start + (end-start)/2;
if(A[mid] == target) {
return mid;
}
if(A[mid] < A[end]) {
// right half sorted
if(target > A[mid] && target <= A[end]) {
return searchRotatedSortedArray(A, mid+1, end, target);
} else {
return searchRotatedSortedArray(A, start, mid-1, target);
}
}
else { // left half sorted
if(target>=A[start] && target<A[mid]) {
return searchRotatedSortedArray(A, start, mid-1, target);
} else {
return searchRotatedSortedArray(A, mid+1, end, target);
}
}
}
};
Previous32. Longest Valid ParenthesesNext34. Find First and Last Position of Element in Sorted Array
Last updated