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

大家好，我是开车的阿Q，自动驾驶的时代已经到来，没时间解释了，快和阿Q一起上车。作为自动驾驶系统工程师，必须要有最好的C++基础，让我们来一起刷题吧。

题目考察的知识点

这道题目主要考察二分查找算法的应用。

题目解答方法的文字分析

给定一个经过旋转的有序数组，要求寻找数组中的最小元素。我们可以利用二分查找算法，通过分析不同情况，逐步缩小搜索范围。

思路步骤如下：

1. 初始化左指针 left 指向数组第一个元素，右指针 right 指向数组最后一个元素。
2. 在每一轮二分查找中，计算中间位置 mid = (left + right) / 2。
3. 根据不同的情况判断最小元素可能所在的区间：情况1：如果左端元素小于右端元素，并且中间元素小于左端元素，说明最小元素在左半部分，将 left 更新为 mid。情况2：如果左端元素小于右端元素，并且中间元素大于右端元素，说明最小元素在右半部分，将 right 更新为 mid。情况3：其他情况，最小元素在当前区间内，将 left 更新为 mid 并跳出循环。
4. 最终返回 heights[left]，即找到的最小元素。

本题解析所用的编程语言

本题解析所用的编程语言是C++。

完整且正确的编程代码

class Solution {
  public:
    int findMin(vector<int>& heights) {
        int left =
            0;                  // 左指针，初始指向数组的第一个元素
        int right = heights.size() -
                    1; // 右指针，初始指向数组的最后一个元素
        int mid;                        // 中间指针

        while (left < right) {
            mid = (left + right) / 2; // 计算中间位置

            // 情况1: 左端小于右端，且中间小于左端，说明最小元素在左半部分
            if (heights[left] < heights[right] && heights[mid] < heights[left]) {
                left = mid; // 更新左指针
            }
            // 情况2: 左端小于右端，且中间大于右端，说明最小元素在右半部分
            else if (heights[left] < heights[right] && heights[mid] > heights[right]) {
                right = mid; // 更新右指针
            }
            // 情况3: 其他情况，说明最小元素在当前区间
            else {
                left = mid; // 更新左指针（这里使用 mid 而不是 right 是为了避免死循环）
                break;      // 退出循环
            }
        }
        return heights[left]; // 返回找到的最小元素
    }
};

您的关注、点赞、收藏就是我创作的动力，三连支持阿Q！