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.
【题目分析】dan'sh
有一个没有重复元素的增序排序的数组，对这个数组进行玄旋转操作，然后在旋转后的数组中找到给定的target，如果找不到则返回-1。
【思路】
在一个有序的数组中查找一个数，最高效的就是二分查找。但是经过旋转操作以后数组分裂成了两段，在每一段中是有序的，这中情况下我们能对它使用二分查找嘛？
既然数组被分成了两段，如果我们使用二分查找能确定目标值在数组的哪段，然后改变查找的范围，那么就可以找到目标值。在二分查找的过程中要先确定中间位置的下标mid，通过中间值与最左边值的比较，我们可以确定中间值在数组中的哪一段，然后我们在比较目标值和中间值的大小，这样就能确定目标值的范围。举个例子如下：
- 目标值为6，nums[mid] = 7 > nums[left]。因此中间值在左边一段，此时nums[left]<target<=nums[mid]，可以确定目标值在左边一段。right = mid；
- nums[mid] = 5 > nums[left]。因此中间值在左边一段，此时target>nums[mid]。left = mid + 1；
- nums[mid] = 6 = nums[left]。因此中间值在左边一段，此时target=nums[mid]。right = mid；
- left = right，找到目标值；
注意：
- 当中间值在数组的左段时，要确定目标值的位置不能这样判断：if(target <= nums[mid])，因为我们发现此时数组右段也是满足这个条件的，因此必须这样判断：if(target <= nums[mid] && target >= nums[left])，这样才能保证目标值位与中间值的左边，对于其他的情况目标值肯定在中间值的右边。
- 同理，当中间值在数组的右段时候，在确定目标值的位置时也要注意类似的情况。
- 这个算法对于一个没有旋转的增序排序数组也是适用的。
【java代码】
public class Solution {
public int search(int[] nums, int target) {
if (nums == null || nums.length == 0) return -1;
int l = 0, r = nums.length - 1;
while (l < r) {
int m = l + (r - l) / 2;
if (nums[m] >= nums[l]) {
if (target <= nums[m] && target >= nums[l]) r = m;
else l = m + 1;
}else {
if (target > nums[m] && target <= nums[r]) l = m + 1;
else r = m;
}
}
return nums[l] == target ? l : -1;
}
}