# 「力扣」第 153 题：旋转排序数组的最小值（中等）
- 题目地址：153. 寻找旋转排序数组中的最小值 (opens new window)；
- 题解地址：二分查找（分析为什么可以一分为二、以及为什么比较 nums[mid] 和 nums[right]） (opens new window)。
# 题目描述
已知一个长度为 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 ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
示例 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.length1 <= n <= 5000-5000 <= nums[i] <= 5000nums中的所有整数 互不相同nums原来是一个升序排序的数组，并进行了1至n次旋转
说明：本题解于 2022 年 8 月 31 日重写。
# 理解题意
「旋转」的定义：把一个数组最开始的若干个元素搬到数组的末尾。
# 分析旋转数组的特点
- 多次旋转等价于旋转一次；
- 只会有一次「转折」，一分为二看，一定有一段是有序的；
- 重点理解 1：最大值和最小值「相邻」：即：最大值的右边，如果有的话，一定是最小值；
- 重点理解 2：如果两点是「上升」的，那么两点之间一定是「上升」的。
下面说明「如果两点是「上升」的，那么两点之间一定是「上升」的」。如图：
「左边」< 「中间」，从 「左边」到「中间」就一定是「上升」的，否则就不是「旋转有序数组」。
# 比较「左边」「中间」还是「中间」「右边」
- 比较「左边」和「中间」会发现最小值可能在前面，也可能在后面
下图都满足「左边」<「中间」，但是左图最小值在后面，右图最小值在前面。
最极端就是上图右边这种情况，最小值在数组的第 1 位。
- 比较「中间」「右边」可以确定最小值的位置
下图都满足「中间」<「右边」，并且最小值都在前面。
最极端的情况下，当「中间」<「右边」时，最小值在「中间」。
所以我们可以通过比较「中间」和「右边」，知道旋转数组的最小值在哪里。如果要比较「中间」和「左边」，需要做一些分类讨论，使得解决问题变得复杂。
提示：看到这里感觉有疑问的朋友，可以回头看看「分析旋转数组的特点」这部分的 4 个特点，在草稿纸上写写画画，就清楚了。
参考代码：
public class Solution {
public int findMin(int[] nums) {
int len = nums.length;
int left = 0;
int right = len - 1;
while (left < right) {
int mid = (left + right) / 2;
if (nums[mid] < nums[right]) {
// 下一轮搜索区间 [left..mid]
right = mid;
} else {
// 因为题目中说：你可以假设数组中不存在重复元素
// 此时一定有 nums[mid] > nums[right]
// 下一轮搜索区间 [mid + 1..right]
left = mid + 1;
}
}
// 一定存在最小元素，因此无需再做判断
return nums[left];
}
}
复杂度分析：
- 时间复杂度：
，这里 是输入数组的长度； - 空间复杂度：
，只使用了常数个临时变量。
作者：liweiwei1419 链接：https://suanfa8.com/binary-search/solutions-1/0153-find-minimum-in-rotated-sorted-array 来源：算法吧 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。