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 duplic
//时间复杂度O(n) public int search(int[] A, int target) { for(int i=0;i<A.length;i++){ if(target==A[i]) return i; } return -1; }
二分法：
public class Solution {
public int search(int[] A,int target){
int first=0,mid,last=A.length;
while(first!=last){
mid=(first+last)/2;
if(target==A[mid])return mid;
if (A[first] <= A[mid]) {
if (A[first] <= target && target < A[mid])//有序部分
last = mid;
else
first = mid + 1;
} else {
if (A[mid] < target && target <= A[last-1])//有序部分
first = mid + 1;
else
last = mid;
}
}
return -1;
}
}
Search in Rotated Sorted Array
原文：http://www.cnblogs.com/gaoxiangde/p/4357275.html