寻找旋转排序数组中的最小值[中等]

在这里插入图片描述

优质博文IT-BLOG-CN

一、题目

已知一个长度为n的数组，预先按照升序排列，经由1到n次旋转后，得到输入数组。例如，原数组nums = [0,1,2,4,5,6,7]在变化后可能得到：
【1】若旋转4次，则可以得到[4,5,6,7,0,1,2]
【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)的算法解决此问题。

示例 1：
输入：nums = [3,4,5,1,2]
输出：1
解释：原数组为[1,2,3,4,5]，旋转3次得到输入数组。

示例 2：
输入：nums = [4,5,6,7,0,1,2]
输出：0
解释：原数组为[0,1,2,4,5,6,7]，旋转3次得到输入数组。

示例 3：
输入：nums = [11,13,15,17]
输出：11
解释：原数组为[11,13,15,17]，旋转4次得到输入数组。

n == nums.length
1 <= n <= 5000
-5000 <= nums[i] <= 5000
nums中的所有整数互不相同
nums原来是一个升序排序的数组，并进行了1至n次旋转

二、代码

二分查找

我们考虑数组中的最后一个元素xxx：在最小值右侧的元素（不包括最后一个元素本身），它们的值一定都严格小于xxx；而在最小值左侧的元素，它们的值一定都严格大于xxx。因此，我们可以根据这一条性质，通过二分查找的方法找出最小值。

在二分查找的每一步中，左边界为low，右边界为high，区间的中点为pivot，最小值就在该区间内。我们将中轴元素nums[pivot]与右边界元素nums[high]进行比较，可能会有以下的三种情况：

第一种情况是nums[pivot]<nums[high]。这说明nums[pivot]是最小值右侧的元素，因此我们可以忽略二分查找区间的右半部分。

第二种情况是nums[pivot]>nums[high]。这说明nums[pivot]是最小值左侧的元素，因此我们可以忽略二分查找区间的左半部分。

由于数组不包含重复元素，并且只要当前的区间长度不为1，pivot就不会与high重合；而如果当前的区间长度为1，这说明我们已经可以结束二分查找了。因此不会存在nums[pivot]=nums[high]的情况。

当二分查找结束时，我们就得到了最小值所在的位置。

class Solution {
    public int findMin(int[] nums) {
        int low = 0;
        int high = nums.length - 1;
        while (low < high) {
            int pivot = low + (high - low) / 2;
            if (nums[pivot] < nums[high]) {
                high = pivot;
            } else {
                low = pivot + 1;
            }
        }
        return nums[low];
    }
}

时间复杂度： 时间复杂度为O(log⁡n)，其中n是数组nums的长度。在二分查找的过程中，每一步会忽略一半的区间，因此时间复杂度为O(log⁡n)。

空间复杂度： O(1)。

主要思路

单调递增的序列：

做了旋转：

用二分法查找，需要始终将目标值（这里是最小值）套住，并不断收缩左边界或右边界。

左、中、右三个位置的值相比较，有以下几种情况：

    左值 < 中值, 中值 < 右值 ：没有旋转，最小值在最左边，可以收缩右边界

            右

         中

     左

左值 > 中值, 中值 < 右值：有旋转，最小值在左半边，可以收缩右边界

左值 < 中值, 中值 > 右值：有旋转，最小值在右半边，可以收缩左边界

左值 > 中值, 中值 > 右值：单调递减，不可能出现

分析前面三种可能的情况，会发现情况1、2是一类，情况3是另一类。
【1】如果中值 < 右值，则最小值在左半边，可以收缩右边界。
【2】如果中值 > 右值，则最小值在右半边，可以收缩左边界。
【3】通过比较中值与右值，可以确定最小值的位置范围，从而决定边界收缩的方向。

而情况1与情况3都是左值 < 中值，但是最小值位置范围却不同，这说明，如果只比较左值与中值，不能确定最小值的位置范围。所以我们需要通过比较中值与右值来确定最小值的位置范围，进而确定边界收缩的方向。

接着分析解法里的一些问题：首先是while循环里的细节问题。这里的循环不变式是left < right, 并且要保证左闭右开区间里面始终套住最小值。

中间位置的计算：mid = left + (right - left) / 2这里整数除法是向下取整的地板除，mid更靠近left，再结合while循环的条件left < right，可以知道left <= mid，mid < right，即在while循环内，mid始终小于right。因此在while循环内，nums[mid]要么大于要么小于nums[right]，不会等于。这样else {right = mid;}这句判断可以改为更精确的else if (nums[mid] < nums[right]) {right = mid;}。

再分析一下while循环退出的条件。

如果输入数组只有一个数，左右边界位置重合，left == right，不会进入while循环，直接输出。

如果输入数组多于一个数，循环到最后，会只剩两个数，nums[left] == nums[mid]，以及nums[right]，这里的位置left == mid == right - 1。

如果nums[left] == nums[mid] > nums[right]，则左边大、右边小，需要执行left = mid + 1，使得left == right，左右边界位置重合，循环结束，nums[left]与nums[right]都保存了最小值。

如果nums[left] == nums[mid] < nums[right]，则左边小、右边大，会执行right = mid，使得left == right，左右边界位置重合，循环结束，nums[left]、nums[mid]、nums[right]都保存了最小值。

细化了的代码：

class Solution {
    public int findMin(int[] nums) {
        int left = 0;
        int right = nums.length - 1;                /* 左闭右闭区间，如果用右开区间则不方便判断右值 */ 
        while (left < right) {                      /* 循环不变式，如果left == right，则循环结束 */
            int mid = left + (right - left) / 2;    /* 地板除，mid更靠近left */
            if (nums[mid] > nums[right]) {          /* 中值 > 右值，最小值在右半边，收缩左边界 */ 
                left = mid + 1;                     /* 因为中值 > 右值，中值肯定不是最小值，左边界可以跨过mid */ 
            } else if (nums[mid] < nums[right]) {   /* 明确中值 < 右值，最小值在左半边，收缩右边界 */ 
                right = mid;                        /* 因为中值 < 右值，中值也可能是最小值，右边界只能取到mid处 */ 
            }
        }
        return nums[left];    /* 循环结束，left == right，最小值输出nums[left]或nums[right]均可 */     
    }
};

再讨论一个问题： 为什么左右不对称？为什么比较mid与right而不比较mid与left？能不能通过比较mid与left来解决问题？

左右不对称的原因是： 这是循环前升序排列的数，左边的数小，右边的数大，而且我们要找的是最小值，肯定是偏向左找，所以左右不对称了。

为什么比较mid与right而不比较mid与left？
具体原因前面已经分析过了，简单讲就是因为我们找最小值，要偏向左找，目标值右边的情况会比较简单，容易区分，所以比较mid与right而不比较mid与left。

那么能不能通过比较mid与left来解决问题？
能，转换思路，不直接找最小值，而是先找最大值，最大值偏右，可以通过比较mid与left来找到最大值，最大值向右移动一位就是最小值了（需要考虑最大值在最右边的情况，右移一位后对数组长度取余）。

以下是先找最大值的代码，可以与前面找最小值的比较：

class Solution {
    public int findMin(int[] nums) {
        int left = 0;
        int right = nums.length - 1; 
        while (left < right) {
            int mid = left + (right - left + 1) / 2;   /* 先加一再除，mid更靠近右边的right */
            if (nums[left] < nums[mid]) {
                left = mid;                            /* 向右移动左边界 */
            } else if (nums[left] > nums[mid]) {
                right = mid - 1;                       /* 向左移动右边界 */
            }
        }
        return nums[(right + 1) % nums.length];    /* 最大值向右移动一位就是最小值了（需要考虑最大值在最右边的情况，右移一位后对数组长度取余） */
    }
};

使用left < right作while循环条件可以很方便推广到数组中有重复元素的情况，只需要在nums[mid] == nums[right]时挪动右边界就行：

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

初始条件是左闭右闭区间，right = nums.size() - 1，那么能否将while循环的条件也选为左闭右闭区间left <= right？

可以的，代码如下：

class Solution {
    public int findMin(int[] nums) {
        int left = 0;
        int right = nums.length - 1; 
        while (left <= right) {                         // 循环的条件选为左闭右闭区间left <= right
            int mid = left + (right - left) / 2;
            if (nums[mid] >= nums[right]) {             // 注意是当中值大于等于右值时，
                left = mid + 1;                         // 将左边界移动到中值的右边
            } else {                                    // 当中值小于右值时
                right = mid;                            // 将右边界移动到中值处
            }
        }
        return nums[right];                             // 最小值返回nums[right]
    }
};

这道题还有其它解法： 始终将nums[mid]与最右边界的数进行比较，相当于在每次裁剪区间之后始终将最右边的数附在新数组的最右边。

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

或者在处理了第一种情况之后，始终将nums[mid]与最左边界的数nums[0]进行比较，即相当于在每次裁剪区间之后始终将最左边的数附在新数组的最左边，再不断处理情况2及情况3。

class Solution:
    def findMin(self, nums: List[int]) -> int:
        left, right = 0, len(nums) - 1
        if nums[left] < nums[right]:
            return nums[left]
        while left < right:
            mid = (left + right) >> 1
            if nums[0] > nums[mid]:
                right = mid
            else:
                left = mid + 1
        return nums[left]