Problem:
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.
Analysis:
Two conditions should be paid attention. One is that before rotated, the array is sorted and the other
is there is no duplicate. We can modify binary search to search rotated array.
Suppose A is the rotated array.
left=0, right=A.length-1, mid=(right+left)/2
Case 1: if A[mid] >A[left], A[left .. mid] is in order.
Case 2: if A[mid] < A[left], A[mid] is also smaller than A[right], therefore A[mid .. right] is in order.
We can easily verify whether the target is in the sorted part or not.
Code:
public class Solution {
public int search(int[] A, int target) {
if(A==null || A.length==0 || A.length==1 && A[0]!=target){
return -1;
}
int left=0;
int right=A.length-1;
while(left<=right){
int mid=(left+right)/2;
if(A[mid]==target){
return mid;
}else if(A[mid]>=A[left]){ // A[left..mid] is sorted.
if(A[left]<=target && target<A[mid]){
right=mid-1;
}else{
left=mid+1;
}
}else{//A[mid..right] is sorted.
if(target<=A[right] && target>A[mid]){
left=mid+1;
}else{
right=mid-1;
}
}
}
return -1;
}
}
