LeeCode 153. 寻找旋转排序数组中的最小值

153. 寻找旋转排序数组中的最小值

难度 中等

已知一个长度为 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) 的算法解决此问题。

示例 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] ，旋转 4 次得到输入数组。
复制代码

示例 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 次旋转

题解

这算是二分查找的改版，不一样的地方就是这是把有序数组拆成两半，然后把大的拼接到小的前面，那我们怎么利用二分查找的性质进行查找呢。拼接之后，大部分还是有序的，假设我们从中间二分之后，那左半部分或有半部分其中之一是有序的，有序部分肯定不会有最小值，无序才有，举个例子

34567012，start = 0，end = 7，mid = (end + start) / 2 = 3

可以发现，左半部分0到3是3456，右半部分4到7是7012，是无序的，最小值肯定在无序部分。利用这个规律，可以对我们二分查找进行改造

• 1、判断右半部分nums[mid] < nums[end]是否有序，当右半部分有序，最小值在无序的左半部分，移动右指针end = mid，为什么不是mid-1，因为如果mid刚好是最小那个元素开始的序列，如果mid-1就错过了最小值，比如5671234，mid指向1，如果end=mid-1就错过了（举反例是最快的证明）。

• 2、当右半部分无序，说明最小值在这边，那么我们就可以移动左指针start = mid + 1，为什么这又是mid+1，也是举个极端的例子，比如右半部分是7012，mid指向7，end指向2，此时满足无序条件，左指针start右移到mid + 1，这样最多移动到有序部分，不会丢掉最小值。

• 3、还有疑问，如果全部都是有序了呢，那岂不是和上面的说法违背了，上面的说法并不是官方的原本说法，但是代码按照官方解答并不好理解才举的例子，具体解析可以参考官方解答寻找旋转排序数组中的最小值 – 寻找旋转排序数组中的最小值 – 力扣（LeetCode） (leetcode-cn.com)

• 4、为什么while循环的条件是start<end，也是举例就明白了，当start=7，end=8，mid=7

  • 第一种情况，nums[mid=start] = 1 < nums[end] = 2，那么会执行end=mid，那就退出循环了，在这种情况下，返回nums[start]是最小值。如果条件改为start<=end，发现退不出循环了！！！

  • 第二种情况，nums[mid=start] = 10 > nums[end] = 1，那么会执行start = mid + 1，也退出了循环，在这种情况下，返回nums[start]是最小值。如果如果条件改为start<=end，此时继续循环，然后start=end=mid，又继续执行循环，又执行tart = mid + 1，才退出循环，此时最小值是nums[start-1]

    怎么形容这种情况呢，我觉得灵活运用或者具体代码具体分析，因为我们改造了二分查找，并不是简单的二分查找代码，修改了指针的移动方式，那相应的判断条件也需要修改，不能生搬硬套。

class Solution {
    public int findMin(int[] nums) {
       int start = 0;//左指针
       int end = nums.length - 1;//右指针
       while(start < end){
           int mid = start + (end - start) / 2;
           if(nums[mid] < nums[end]){//右半部分有序，最小值在无序的左半部分，右指针左移
               end = mid;
           }else{//左半部分有序，最小值在无序的右半部分，左指针右移
               start = mid + 1;
           }
       }
       return nums[start];
    }
}
复制代码