Search in Rotated Sorted Array
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 its index, otherwise return -1.
You may assume no duplicate exists in the array.
class Solution {
int process(int A[], int const start, int const end, int const target){
if (start == end){
if (target == A[start]) return start;
else return -1;
}
int const half = start + (end-start)/2;
if ( A[start] <= A[half] && (target <= A[half] && target >= A[start])
|| A[start] > A[half] && (target <= A[half] || target >= A[start])) return process(A, start, half, target);
else return process(A, half+1, end, target);
}
public:
int search(int A[], int n, int target) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
return process(A, 0, n-1, target);
}
};
II
Search in Rotated Sorted Array II
Follow up for "Search in Rotated Sorted Array":
What if duplicates are allowed?
Would this affect the run-time complexity? How and why?
Write a function to determine if a given target is in the array.
class Solution {//with dups, one may not be able to determine to process whether the first half
//or the second half of the array, by just looking at three positions: start, half and end
//e.g. 11111111131
//in this case, both parts must be considered, which rise the worst case to O(n)
bool process(int A[], int const start, int const end, int const target){
if (start == end){
if (target == A[start]) return true;
else return false;
}
int const half = start + (end-start)/2;
if (A[start] == A[half] && A[half] == A[end]) return (process(A, start, half, target) || process(A, half+1, end, target));
if ( A[start] <= A[half] && (target <= A[half] && target >= A[start])
|| A[start] > A[half] && (target <= A[half] || target >= A[start])) return process(A, start, half, target);
else return process(A, half+1, end, target);
}
public:
bool search(int A[], int n, int target) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
return process(A,0,n-1, target);
}
};
