153. 寻找旋转排序数组中的最小值：旋转排序数组性质 与 二分查找算法.md

题目简述：

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：

• 若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
• 若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]

注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。

给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

题目链接：153. 寻找旋转排序数组中的最小值

思路

在第 33 题的解决方案中，我给出了这一重要结论：对于严格单调的旋转数组，任意多次旋转操作均可等价为单次旋转。即，对于严格单调序列 $A$ 及其任意旋转结果 $R^k(A)$（表示旋转 $k$ 次后的数组），存在一个旋转次数 $m\in[0,n−1]$（其中 $n$ 为数组长度），使得： $$ R^k(A)=R^m(A) $$ 且 $m$ 被 $m\equiv k\mod n$ 唯一确定。

参见：Cormen, T. H., et al. (2009). Introduction to Algorithms (3rd ed.). MIT Press.

---

简而言之，严格单调的旋转数组无论旋转多少次，都可以被视为只进行了一次特殊的旋转。也就是说，任意次的旋转结果，都一定存在一个仅进行一次的旋转，二者结果完全相同。但是要注意处理多次翻转后数组回到原样的特殊情况。

---

那么该问题就成了一个二分查找问题：旋转数组一定是先严格单调递增，在一次突然骤降后再次严格单调递增直至数组尽头的。因此，最小元素位于那次突然骤降的位置，因为如果我们视旋转数组仅进行了一次旋转，那么该位置上的元素原本是旋转前排序数组的第一个元素，当然也就是全局最小的元素。

旋转后，要么仍保持单调，要么存在唯一的拐点，该拐点即为全局最小值点，同时拐点左侧的元素均大于拐点右侧的元素。

应该能想象到形状了吧？

明确了这一点，这就只是一个简单的二分查找变种问题了。

关于算法设计的细节，我将在代码的注释中详细说明，就不在这里赘述了。

代码

class Solution {
    public int findMin(int[] nums) {

        int left = 0;
        int right = nums.length - 1;
        int mid;
        int pivot = nums[nums.length - 1];

        // 如果左端点小于右端点，则旋转排序数组一定严格单调递增
        if (nums[left] <= nums[right]) return nums[left];  // 等号处理了 n = 1 的情况

        // 其他任何情况，均可以视为旋转排序数组仅进行一次旋转
        while (true) {
            if (right == left + 1) return Math.min(nums[left], nums[right]);
            
            mid = left + ((right - left) >> 1);  // 避免溢出
            // 通过 pivot = nums[n - 1] 可判断 mid 与最小元素的相对位置关系
            // 如果 nums[mid] > pivot，则最小元素位于 mid 右侧
            if (nums[mid] > pivot) {
                left = mid;
            } else {
                if (nums[mid] < nums[mid - 1]) return nums[mid];
                right = mid;
            }
        }
    }
}

改进写法

if (right == left + 1) return Math.min(nums[left], nums[right]); 的处理总让人觉得不够优雅，我们可以换成更标准、更优雅的二分查找实现来写算法：

class Solution {
    public int findMin(int[] nums) {
        
        int left = 0;
        int right = nums.length - 1;
        
        if (nums[left] <= nums[right]) return nums[left];
        
        while (left < right) {
            int mid = left + ((right - left) >> 1);
            if (nums[mid] > nums[right]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return nums[left];
    }
}