在转动的有序数组中寻找目标值

题目描述

给出一个转动过的有序数组，你事先不知道该数组转动了多少

(例如,0 1 2 4 5 6 7可能变为4 5 6 7 0 1 2).

在数组中搜索给出的目标值，如果能在数组中找到，返回它的索引，否则返回-1。

假设数组中不存在重复项。

示例1

输入

[1],0
           

返回值

-1
           

示例2

输入

[3,2,1],1
           

返回值

2
           

class Solution {
public:
    // 不要被“旋转”而迷惑，“有序”并不是二分查找的核心
    // 二分查找的核心是"通过界桩快速决定查找方向，大幅缩短查找空间"
    // 只要能快速确定界桩，就能使用二分查找
    // 充分利用有序数组能够快速获取边界值的特性
    // 利用这一特性可以快速确定目标值应处的区间
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while(left <= right){
            int mid = (right - left) >> 2;
            if(target == nums[mid]){
                return mid;
            }
            //左边有序
            if(nums[left] <= nums[mid]){
                //如果target 在左边有序序列中间
                if( target < nums[mid] && target >= nums[left]){
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else if(nums[right] >= nums[mid]){
                if( target > nums[mid] && nums[right] >= target){
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        return -1;
    }
};