开启掘金成长之旅！这是我参与「掘金日新计划 · 2 月更文挑战」的第 2 天，点击查看活动详情

一、题目描述

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [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

二、思路讲解

1、方法一（暴力查找）

对于算法小白来说，暴力查找不失为一种好的解题方法，就是不一定每题都能用。

可以看出，数组旋转之后，必然会变成先递增、忽然变小、再递增的形式，那么，我们可以遍历数组，找到忽然变小的地方，就是我们要找到值。

2、方法二（二分查找）

一说到查找，二分查找的效率无疑是很高的。

上面说到， 数组旋转后变成先递增、忽然变小、再递增的形式，并且，最小值右侧的最大值必然小于左侧的最小值。

那么，我们分别定义前后指针low、high，中间的指针center，比较numbers[center]和numbers[high]的大小。假如：

1.numbers[center] < numbers[high]，说明最小值在center的左侧，则可以忽略center右侧的所有数；

2.numbers[center] > numbers[high]，说明最小值在center的右侧，则可以忽略center左侧的所有数；

3.numbers[center] = numbers[high]

并不好判断最小值究竟在center左侧还是右侧，那么，我们就把high指针左移一位，继续二分，直到出现 numbers[center] 和 numbers[high] 的值不相等为止。

三、Java代码实现

1、方法一

class Solution {
    public int minArray(int[] numbers) {
 
        //遍历numbers
		for(int i=0; i<numbers.length-1; i++) {
			//如果出现突然变小的数字，则就是我们要找的
			if(numbers[i] > numbers[i+1]) {
				return numbers[i+1];
			}
		}
		//如果跳出循环，说明没有突然变小的数字，则返回第一个数字
		return numbers[0];
    }
}

2、方法二

class Solution {
    public int minArray(int[] numbers) {
 
        int low = 0;
        int high = numbers.length - 1;
 
        while (low < high) {
            //二分
            int center = low + (high - low) / 2;
 
            if (numbers[center] < numbers[high]) {    //忽略center右侧
                high = center;
            } else if (numbers[center] > numbers[high]) {    //忽略center左侧
                low = center+ 1;
            } else {    //high左移一位
                high -= 1;
            }
        }
        return numbers[low];
    }
}

四、时空复杂度分析

1、方法一

时间复杂度O(n) ：遍历了一次numbers数组

空间复杂度O(1)

2、方法二

时间复杂度O(log n) ：二分查找了一次numbers数组

空间复杂度O(1)