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.
Example
For [4, 5, 1, 2, 3] and target=1, return 2.
For [4, 5, 1, 2, 3] and target=0, return -1
.
旋转数组，这道题有点绕，但是本质还是二分查找，只是要多加几重判断。
当我们找到mid后，我们要去判断mid左边是排序好的数组，还是右边是排好的数组。
具体做法是用中间值mid去比较start值，如果大于，就说明左边是排好的，如果是小于那就说明右边是排好的。
进而查看target是否在排好序的范围内，从而决定往那边走。
public class Solution {
/**
*@param A : an integer rotated sorted array
*@param target : an integer to be searched
*return : an integer
*/
public int search(int[] A, int target) {
// write your code here
if (A == null || A.length == 0) {
return -1;
}
int start = 0, end = A.length-1;
while( start <= end) {
int mid = (end + start)/2;
if (A[mid] == target){
return mid;
}
if (A[mid] <= A[start]){ // right side is sorted
if(A[mid] < target && target <= A[end] ){
start = mid + 1;
}else{
end = mid -1;
}
}else{ //left side is sorted
if(A[start] <= target && target < A[mid]){
end = mid - 1;
}else{
start = mid + 1;
}
}
}
return -1;
}
}
