题目描述

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。

示例 1：
输入：[3,4,5,1,2]
输出：1示例 2：
输入：[1,1,1,0,1]
输出：0示例3：
输入：[1,0,1,1,1]
输出：0示例4：
输入：[1,2,3,4,5]
输出：1

题解

根据题目描述得出：给定数组由两个排好序的数组组成，而且满足左数组所有元素大于等于右数组所有元素。

题目要求的数组中最小元素，也就是右排序数组中的第一个元素。

所以可以采用二分法的思路来做，初始化 $left = 0$, $right = numbers.length - 1$ 。计算中点的下标 $medium = (left + right) / 2$ ，并判断中点的值和右边值的关系：

• 如果numbers[medium] > numbers[right]，说明medium正处于左数组，将left设为medium + 1。
• 如果numbers[medium] < numbers[right]，说明medium正处于右数组，将right设为medium（这时不能设置为medium - 1，因为目标是求右数组的第一个元素，medium已经在右数组里了，如果将medium - 1就可能出界到左数组中）
• 如果numbers[medium] == numbers[right]，比如[1,0,1,1,1]或[1,1,1,0,1]。这时最小元素可能在左边，也可能在右边，所以直接顺序遍历left到right中的所有元素即可。

class Solution {public int minArray(int[] numbers) {int left = 0, right = numbers.length - 1;while (left < right){int medium = (left + right ) / 2;if (numbers[medium] > numbers[right]) {left = medium + 1;} else if (numbers[medium] < numbers[right]) {right = medium;} else {return findMin(numbers, left, right);}}return numbers[left];}private static int findMin(int [] numbers, int left, int right) {int min = 0x3f3f3f3f;for (int i = left ; i <= right ; i++) {if (min > numbers[i]) {min = numbers[i];}}return min;}
}

时间复杂度：$O(log(n))$。

空间复杂度：$O(1)$。