假设按照升序排序的数组在预先未知的某个点上进行了旋转。 ( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

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

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

    你的算法时间复杂度必须是 O(log n) 级别。

    示例 1:

    输入: nums = [4,5,6,7,0,1,2], target = 0
    输出: 4
    示例 2:

    输入: nums = [4,5,6,7,0,1,2], target = 3
    输出: -1
    image.png
    原理示意图

    1. class Solution {
    2. public:
    3.     int search(vector<int>& nums, int target) {
    4.         int n = nums.size();
    5.         if (0 == n) return -1;
    6.         if (1 == n) return nums[0] == target ? 0 : -1;
    7.         int left = 0;
    8.         int right = n-1;
    9.         while(left <= right){
    10.             int mid = (left + right) >> 1;
    11.             if (nums[mid] == target) return mid;
    12.             if (nums[left] <= nums[mid]){                     // [left, mid]有序 
    13.                 if(nums[left] <= target && target < nums[mid])// target位于[left, mid)之间
    14.                     right = mid-1;                            // 更新right
    15.                 else
    16.                     left = mid+1;                             // 否则，更新left
    17.             }
    18.             else                         // nums[left] > nums[mid]表明[mid+1, right]有序 
    19.             {
    20.                 if (nums[mid] < target && target <= nums[right])//target位于(mid,right]之间
    21.                     left = mid+1;                             // 更新left
    22.                 else
    23.                     right = mid-1;                            // 否则，更新right
    24.             }
    25.         }
    26.         return -1;
    27.     }
    28. };

    欢迎交流，批评指正！