根据以上方法，每次我们都可以切掉一半的数据，所以算法的时间复杂度是O(logn)，空间复杂度是O(1)。代码如下：
public int search(int[] A, int target) {
if(A==null || A.length==0)
return -1;
int l = 0;
int r = A.length-1;
while(l<=r)
{
int m = (l+r)/2;
if(target == A[m])
return m;
if(A[m]<A[r])
{
if(target>A[m] && target<=A[r])
l = m+1;
else
r = m-1;
}
else
{
if(target>=A[l] && target<A[m])
r = m-1;
else
l = m+1;
}
}
return -1;
}注意在这道题中我们假设了这个数组中不会出现重复元素。如果允许出现重复元素，那么我们要对中间和边缘的相等的情况继续处理，进而影响到时间复杂度，这个问题会在Search
in Rotated Sorted Array II中具体讨论，大家有兴趣可以看看。Search in Rotated Sorted Array -- LeetCode,布布扣,bubuko.com
Search in Rotated Sorted Array -- LeetCode
原文：http://blog.csdn.net/linhuanmars/article/details/20525681