81. Search in Rotated Sorted Array II
1.問題
一個sorted array在某個pivot旋轉後, 給予一個數字, 判斷他是否存在

2.想法
提問:
function header, parameter
test input
說明想法
binary search
當mid值大於left值時, 表示左半部已經排序, 先判斷目標是否在左半部, 若是則開始搜尋左半部, 若否則開始搜尋右半部
當mid值小於left值時, 表示右半部已經排序, 先判斷目標是否在右半部, 若是則開始搜尋右半部, 若否則開始搜尋左半部
若都不是, 表示mid等於left, 表示重複直, 則回到線性搜尋
測試計算複雜度
3.程式碼
class Solution {
public:
bool search(vector<int>& nums, int target) {
int index = searchRotatedSortedArray(nums, 0, nums.size() - 1, target);
return (index == -1) ? false : true;
}
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 if (A[mid] > A[end]){ // 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);
}
} else {
return searchRotatedSortedArray(A, start, end-1, target);
}
}
};
Last updated