📗difficulty：Easy
🎯Tags：
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。
示例 1：
输入：[3,4,5,1,2]
输出：1
示例 2：
输入：[2,2,2,0,1]
输出：0
以下思路来源于 leetcode-cn 用户 Krehets 的题解，这里对其进行抄录，感谢其的精彩分析。
一种简单的且直观的办法是从头到尾遍历一次数组，就可以找出最小值来。但是这种情况的时间复杂度为 O(n) ，并没有利用题目给出的旋转后的数组的特性。
题目中描述到，给定一个升序的数组，然后再进行旋转操作。如果一个数组是有序的，那么查找一个元素可以采用两分搜索的办法，其复杂度为 O(log n)，本题目中数组旋转后，变成了 2 个有序的数组，但是依旧保留有部分特殊性质，可以尝试利用其性质。
旋转后的数组，左半部分的任意一个数 ，都大于等于右半部分的数。而且最小的元素，就是左右两部分的分界线。
设置指针 left 和 right 分别指向数组的两端。mid 为两分的中点。mid 为向下取整计算得出。
有以下三种的情况：
- 当
numbers[mid] > numbers[right]时mid在左半部分，即旋转点 p 一定在[mid + 1,right]中，所以执行left = mid + 1。
- 当
numbers[mid] < numbers[right]时mid在右半部分，即旋转点 p 一定在[left,mid]中，所以执行right = mid。
- 当
numbers[mid] == numbers[right]时- 此时无法判断
mid在哪个部分中，例如：- 例
[1,0,1,1,1]：旋转点 p = 1 ，而 mid = 2 在 右排序数组 中。 例[1,1,1,0,1]：旋转点 p = 3 ，而 mid = 2 在 左排序数组 中。
- 例
- 这也是本题的难点所在。解决的办法是执行
right = right - 1，缩小判断的范围。- 解析：执行
right - 1后，旋转点 p 依旧在[left,right]区间内。 - 如果
mid在右排序数组中，numbers[mid] == numbers[right]，因此数组[mid,right]区间内的所有元素都相等，而right - 1后，旋转点 p 依旧在[left,right]区间内。 - 如果
mid在左排序数组中，有numbers[p] <= numbers[right] == numbers[mid]。- 若
numbers[p] < numbers[right]，这说明 right 的左边还有更小的数字，执行right - 1还能保证旋转点 p 在[left,right]内。 - 若
numbers[p] == numbers[right]的情况下。- 当
right > p，right - 1后旋转点依旧在[left,right]内。例如：[1,1,1,0,1] - 当
right = p时，执行righ - 1后，可能丢失旋转点，即 p 不在[left,right]的范围内。例如：[1,1,1,2,3,1]。此时 left = 0，right = 5，p = 5。虽然丢失了旋转点 p 的索引值，但是之后的循环都是在执行right = mid，最终返回值为numbers[left]，其值和number[p]相等。
- 当
- 若
- 解析：执行
- 综上所述，此方法可以保证返回值
numbers[left]一定为旋转点的值；某些情况下会 left 的索引不是旋转点 p 的值，但是此方法是可行的。
- 此时无法判断
// 代码虽然简洁，但是本题需要分情况讨论，比较难以考虑
public int minArray(int[] numbers) {
if (numbers == null || numbers.length == 0) {
return -1;
}
int left = 0;
int right = numbers.length -1;
int mid;
while (left < right) {
mid = left + (right - left) / 2;
if (numbers[mid] > numbers[right]) {
left = mid + 1;
} else if (numbers[mid] < numbers[right]) {
right = mid;
} else {
right--; // 简约而不简单
}
}
return numbers[left]; // 简约而不简单
}- 时间复杂度：
O(log n)，特殊情况下会退化到O(n)。 - 空间复杂度：
O(1)。
诚然，上面分析的两分查找，能够给出正确的答案，但是其思路解析并不够完善，下面给出更加容易思考且理解的解读。
以下分析来自 leetcode-cn 用户的题解。
public class Solution {
// [3, 4, 5, 1, 2]
// [1, 2, 3, 4, 5]
// 不能使用左边数与中间数比较，这种做法不能有效地减治
// [1, 2, 3, 4, 5]
// [3, 4, 5, 1, 2]
// [2, 3, 4, 5 ,1]
public int minArray(int[] numbers) {
int len = numbers.length;
if (len == 0) {
return 0;
}
int left = 0;
int right = len - 1;
while (left < right) {
int mid = (left + right) >>> 1;
if (numbers[mid] > numbers[right]) {
// [3, 4, 5, 1, 2]，mid 以及 mid 的左边一定不是最小数字
// 下一轮搜索区间是 [mid + 1, right]
left = mid + 1;
} else if (numbers[mid] == numbers[right]) {
// 只能把 right 排除掉，下一轮搜索区间是 [left, right - 1]
right = right - 1;
} else {
// 此时 numbers[mid] < numbers[right]
// mid 的右边一定不是最小数字，mid 有可能是，下一轮搜索区间是 [left, mid]
right = mid;
}
}
// 最小数字一定在数组中，因此不用后处理
return numbers[left];
}
}使用减治的思想来解决两分查找的问题，有神奇效果。
154. 寻找旋转排序数组中的最小值 II 和本题描述等完全一致，代码可以相互通用。
153. 寻找旋转排序数组中的最小值 是一个情况稍微简单的情况，其保证输入数组中，不含有重复的元素。使用 154 题的代码也可以正常通过测试。
在这种情况下的分析如下：
- 当
numbers[mid] < numbers[right]时，旋转点在左边序列，执行right = mid - 当
numbers[mid] > numbers[right]时，旋转点在右边序列，执行left = mid + 1
最终返回 numbers[left] 。
public int findMin(int[] numbers) {
if (numbers == null || numbers.length == 0) {
return -1;
}
int left = 0;
int right = numbers.length -1;
int mid;
while (left < right) {
mid = left + (right - left) / 2;
if (numbers[mid] > numbers[right]) {
left = mid + 1;
} else if (numbers[mid] < numbers[right]) {
right = mid;
}
}
return numbers[left];
}- 时间复杂度：
O(log n)。 - 空间复杂度：
O(1)。
- 考察应聘者对二分查找的理解。本题交换了二分查找的条件，输入的数组不是排序的，而是排序数组的一个旋转。这要求我们对两分查找的过程有深刻的理解。
- 考察应聘者的沟通和学习能力。面试官给出了一个新的概念：数组的旋转。需要我们在很短的时间内学习、理解这个新的概念。在面试的过程中，如果面试官给出新的概念，那么我们可以主动和面试官进行沟通，多问几个问题，把概念弄清楚。
- 考察应聘者思维的全面性。排序数组本身是数组旋转的一个特例。另外，我们要考虑到数组中有相同数字的特例。如果不能很好地处理这些特例，就很难写出让面试官满意的完美代码。