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.
Solution:
public int help(int[] A, int target,int start, int end)
{
if(start>end)
{
return -1;
}
int mid = (start+end)/2;
if(A[mid] == target)
return mid;
else if((A[mid]>A[end]&&target>A[end]&&target<A[mid])||(A[mid]<A[end]&&(target<A[mid]||target>A[end])))
return help(A,target, start, mid-1);
else
return help(A,target, mid+1, end);
}
public int search(int[] A, int target) {
if(A.length==0)
return -1;
return help(A,target, 0, A.length-1);
}
No comments:
Post a Comment