Suppose an array sorted in ascending order 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.
Your algorithm's runtime complexity must be in the order of O(log n).
Example 1:
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
题目
假设有一个升序排列的数组，但是随机的旋转了几位，具体旋转了多少不知道，现在让我们找到数组中的特定元素，返回索引值。要求时间复杂度为 O(log n)
思路
数组本身有序，但是旋转以后，就变成了局部有序。时间复杂度要求 O(log n)，即要是用二分法。所以问题就二分后怎么选取下一步区间的问题。
首先数组一分为二，获取mid，无论数组怎么旋转，肯定有半边是有序的。
所以判断一下nums[mid]和nums[0]的大小，
- 如果nums[mid]>=nums[0]，说明数组左边是升序的，再以此为前提，继续判断：
- nums[0]<=target<nums[mid]：则在[0,mid-1]里找;
- 否则在[mid+1,len-1]里找。
- 如果nums[mid]<nums[0]，说明数组右边是升序的，再以此为前提，继续判断：
- nums[len]>=target>nums[mid]：则在[mid+1,len-1]里找;
- 否则在[0,mid-1]里找
最后注意一下边界条件：mid可能会等于0，target也可能等于每一次缩小范围的边界上的数，所以可以加以判断，减少计算
代码
int len=nums.length;
int l=0;
int r=len-1;
while (l<=r) {
int mid=(l+r)/2;
if (nums[mid]==target) {
return mid;
}
if (nums[mid]>=nums[0]) {//左半边是递增的
if (target==nums[l]) {
return l;
}
if (nums[mid]>target&&target>nums[0]) {//在左边找
r=mid-1;
}else {
l=mid+1;//在右边找
}
}else {//右半边是递增的
if (target==nums[r]) {
return r;
}
if (nums[mid]<target&&target<nums[len-1]) {
l=mid+1;
}else {
r=mid-1;
}
}
}
return -1;
