题解 | 旋转数组的最小数字

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型vector
     * @return int整型
     */
    int minNumberInRotateArray(vector<int>& nums) {
        int left = 0;
        int right = nums.size() - 1;

        while (left < right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] > nums[right]) {
                // 最小值在右侧
                left = mid + 1;
            } else if (nums[mid] < nums[right]) {
                // 最小值在左侧或就是mid
                right = mid;
            } else {
                // 当 nums[mid] == nums[right] 时，无法判断，缩小右边界
                right--;
            }
        }

        return nums[left];
    }
};

算法思路
旋转数组由两个有序部分组成，最小值位于第二个有序部分的开头。
使用二分查找，比较中间元素与右端元素：
如果中间元素大于右端元素，说明最小值在右侧，将左指针移动到中间位置右边。
如果中间元素小于右端元素，说明最小值在左侧或就是中间元素，将右指针移动到中间位置。
如果中间元素等于右端元素，无法判断最小值在哪侧，但通过将右指针减一缩小范围，不会错过最小值。
当左指针和右指针相遇时，指向的元素即为最小值。

1. 旋转数组的特性
旋转数组虽然整体不是有序的，但它具有部分有序性：
由两个有序子数组拼接而成
左半部分的所有元素 ≥ 右半部分的所有元素
最小值正好是两个有序子数组的分界点

2. 二分查找的本质
二分查找并不要求整个数组完全有序，只需要能够通过中间元素判断目标值在哪一侧。旋转数组正好满足这个条件：
通过比较 nums[mid] 和 nums[right]，可以确定最小值在哪一半

4. 为什么不是其他方法？
暴力搜索 O(n)：太慢，不符合 O(logn) 要求
排序 O(nlogn)：破坏了原始信息，且比要求的更慢
归并排序 O(nlogn)：虽然能排序，但时间复杂度不满足要求

5. 思维过程
识别模式：旋转数组 = 两个有序子数组
寻找突破口：最小值是分界点
利用有序性：虽然整体无序，但局部有序
设计比较策略：通过与端点比较来确定搜索方向
验证可行性：每次迭代都能将搜索范围减半

6. 类似问题模式
这种思路在很多"部分有序"或"旋转"问题中都适用：
在旋转数组中搜索目标值
寻找峰值元素
在山脉数组中查找目标值

核心思想
二分查找的关键在于：能够通过中间元素确定目标在哪一半，而不要求整个数组完全有序。
在旋转数组问题中，我们找到了一个聪明的比较策略（与右端点比较），使得即使数组不完全有序，也能每次排除一半的搜索空间。