假设按照升序排序的数组在预先未知的某个关键点上旋转。

（即 0 1 2 4 5 6 7 将变成 4 5 6 7 0 1 2）。

给你一个目标值来搜索，如果数组中存在这个数则返回它的索引，否则返回 -1。

你可以假设数组中不存在重复。

详见：https://leetcode.com/problems/search-in-rotated-sorted-array/description/

Java实现：

class Solution {    public int search(int[] nums, int target) {        int size=nums.length;        if(size==0||nums==null){            return -1;        }        int left=0;        int right=size-1;        while(left<=right){            int mid=(left+right)>>1;            if(nums[mid]==target){                return mid;            }else if(nums[mid]
     
      =target){                    left=mid+1;                }else{                    right=mid-1;                }            }else{                if(nums[left]<=target&&nums[mid]>target){                    right=mid-1;                }else{                    left=mid+1;                }            }        }        return -1;    }}
     

 C++实现：

class Solution {public:    int search(vector
     
      & nums, int target) {        int size=nums.size();        if(size==0||nums.empty())        {            return -1;        }        int left=0;        int right=size-1;        while(left<=right)        {            int mid=(left+right)/2;            if(nums[mid]==target)            {                return mid;            }            else if(nums[mid]
      
       =target)                {                    left=mid+1;                }                else                {                    right=mid-1;                }            }            else            {                if(nums[left]<=target&&nums[mid]>target)                {                    right=mid-1;                }                else                {                    left=mid+1;                }            }        }        return -1;    }};