在轉動的有序數組中尋找目标值

題目描述

給出一個轉動過的有序數組，你事先不知道該數組轉動了多少

(例如,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;
    }
};