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

考察知识点：二分

题目分析：

可以将图画出来，以便观察规律。

假设有一个单调下降且每个数都不相同的数组，它旋转后就会变成下图所示的样子：

那我们应该想办法找到上图中发生突变的点。首先我们应该先看序列中最中间的数。如果这个数的前一个数比它大，后一个数比他小，那么它就不是我们想要的结果。这次判断能排除哪一部分的结点呢？我们观察图像，发现当中间的数在靠左边的梯形上时，它的值一定比序列中第一个数小。当中间的数在靠右边的梯形上时，它的值一定比序列中第一个数大。可以根据这个规律判断是排除左边的元素还是右边的元素。

当一个数的左边比较大，右边也比较大时，说明我们找到了答案。

所用编程语言：C++

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