题解 | #在旋转过的有序数组中寻找目标值#

本题运用了二分查找的知识点

对数组进行二分查找的前提条件是，数组必须单调，现在 把数组的序列前后调换了， 就破坏了这个单调性

但是，如果能找到 数组旋转的分界点，就能转化为对两个子数组进行二分查找的问题了

题目的条件就是 整个数组的元素是单调的， 所以 第一个数组元素 一定比其他数组元素都要小

因此转化为 找到 第一个 nums[i], 满足 nums[i] < nums[0], 那么 i 就是旋转分界点

找到分界点后， target一定在分界点的左边或者右边，判断子数组端点元素可以确定，然后直接可以使用二分查找。

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型vector
     * @param target int整型
     * @return int整型
     */
    int search(vector<int>& nums, int target) {
        // write code here
        // 寻找第一个比 nums[0] 小的数
        int n = nums.size();
        if (!n) return -1;
        int l = 0, r = n - 1;
        while (l < r) {
            int m = l + (r - l) / 2;
            if (nums[m] >= nums[0]) {
                l = m + 1;
            } else {
                // nums[m] < nums[0]
                r = m;

            }
        }
        //first element
        if (nums[r] == target) return r;
        if (nums[r] > target) return -1;
        if (nums[n - 1] >= target ) {
            l = r, r = n - 1;
        } else {
            //nums[n-1]<target
            l = 0, r = r - 1;
        }
        while (l < r) {
            int m = l + (r - l) / 2;
            if (nums[m] >= target)
                r = m;
            else
                l = m + 1;
        }
        return r < 0 ? -1 : nums[r] == target ? r : -1;

    }
};




#ifdef debug


int main() {
    cout << " * " << endl;
    Solution k;
    vector<int>  arr  {6, 8, 10, 0, 2, 4};
    cout << "result:  " << k.search(arr, 10) << endl;
    return 0;
}


#endif