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.

 

二分搜索，好好理解里面的逻辑吧。

1 class Solution { 2 public: 3     int search(vector
     
      & nums, int target) { 4         if(nums.size()==0) return -1; 5         int left=0,right=nums.size()-1; 6         while(left<=right) 7         { 8             int mid = (left+right)/2; 9             if(nums[mid]==target) return mid;10             if(nums[mid]>nums[left])11             {12                 if(target <= nums[mid] && target >= nums[left]) right = mid - 1;13                 else left = mid + 1;14             }15             else if(nums[mid]
      
       = nums[left] || target <= nums[mid]) right = mid -1;18                 else left = mid + 1;19             }20             else left ++;21         }22         return -1;23     }24 };