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.

 

分析：

 

给出一个旋转的有序数组，所谓的旋转就是在原有的有序数组某个位置把数组分为两部分，把后半部分平移到前面来。

比如： 0  1  2   4  5  6   7  ，

从2和4之间分开，前半部分是0   1   2 ，后半部分是 4   5  6   7  ，把后面的前移变成了 4  5  6  7  0   1  2  。

寻找target的时候，分为两种情况。

（1）mid在第一个上升区间，也就是4  5  6  7 。

        如果在这个区间，那么nums[start]是小于nums[mid]的。寻找target分了两种情况，

       第一种，target在start和mid之间，也就是在第一个上升区间的前半部分，这样将end结点前移。

       第二种，target不在start和mid之间，start后移。

（2）mid在第二个上升区间，也就是 0  1  2 

       如果在这个区间呢，那么nums[mid]是小于nums[end]的。寻找target分了两种情况，

       第一种，target在mid和end之间，也就是在第二个上升区间的后半部分，这样将start结点后移。

       第二种，target不在mid和end之间，end前移。

 

public class Solution {    public int search(int[] nums, int target) {        if (nums.length == 0){            return -1;        }                int start = 0, end = nums.length - 1;                while (start + 1 < end){            int mid = start + (end - start)/2;            if(nums[mid] == target){                return mid;            }            if (nums[start] < nums[mid]){                if (target >= nums[start] && target <= nums[mid]){                    end = mid;                }else{                    start = mid;                }            }else{                if (target >= nums[mid] && target <= nums[end]){                    start = mid;                }else{                    end = mid;                }            }        }        if (nums[start] == target){            return start;        }        if (nums[end] == target){            return end;        }        return -1;    }}

 

 

 

 

附图，有点丑，不知道会不会掉粉～