题解 | #旋转排列之找出最矮的牛# 二分

知识点

二分

思路

首先特判首位两个元素的大小来排除没有移动的情况。

在移动后，数组变成了两段递减的拼接，我们需要找到第一段的末尾，可以使用二分，如果当前的mid元素比首元素要大，那么在mid右端的部分将舍弃。

每次会减少一半的范围。所以时间复杂度为

AC Code（C++）

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