题解 | #旋转位置的特定牛# 两次二分

知识点

二分

思路

首先和 NB79 旋转排列之找出最矮的牛这道题一样找到分界点，分界点两边都是有序的，可以直接二分查找是否存在对应的值。即两次二分，时间复杂度

AC Code（C++）

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @param target int整型 
     * @return int整型
     */
    int search(vector<int>& nums, int target) {
        int l = 0, r = nums.size() - 1;
        while (l < r) {
            int mid = (l + r + 1) >> 1;
            if (nums[mid] > nums[0]) r = mid - 1;
            else l = mid;
        }
        int index = l;
        // 找到了分界点l [0, l] [l+1, n-1]
        if (target <= nums[0]) l = 0, r = index;
        else l = index + 1, r = nums.size() - 1;
        return find(nums, l, r, target);
    }
    int find(vector<int>& nums, int l, int r, int x) {
        while (l < r) {
            int mid = (l + r + 1) >> 1;
            if (nums[mid] < x) r = mid - 1;
            else l = mid;
        }
        return nums[l] == x ? l : -1;
    }
};