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.

1 // better one from discuss  2 class Solution { 3 public: 4     int search(vector
     
      & nums, int target) { 5         int ret = -1; 6         int start = 0; 7         int mid; 8         int end = nums.size() - 1; 9         10         while (start <= end){11             mid = (start + end) / 2;12             if (target == nums[mid]){13                 return mid;14             }15             16             if (nums[start] <= nums[mid]){17                 if ((nums[start] <= target) && (target < nums[mid])){18                     end = mid - 1;19                 }else{20                     start = mid + 1;21                 }22             }else{
   // if (nums[mid] <= nums[end]){
    23                 if ((nums[mid] < target) && (target <= nums[end])){24                     start = mid + 1;25                 }else{26                     end = mid - 1;27                 }28             }29         }30         31         return ret;32     }33 };