旋转数组的最小数字

描述

有一个长度为 n 的非降序数组，比如[1,2,3,4,5]，将它进行旋转，即把一个数组最开始的若干个元素搬到数组的末尾，变成一个旋转数组，比如变成了[3,4,5,1,2]，或者[4,5,1,2,3]这样的。请问，给定这样一个旋转数组，求数组中的最小值。

数据范围：$1\le n\le 10000$，数组中任意元素的值: $0\le val\le 10000$

要求：空间复杂度：$O(1)$ ，时间复杂度：$O(logn)$

示例1

输入：

[3,4,5,1,2]

返回值：

1

示例2

输入：

[3,100,200,3]

返回值：

3

思路

第一个很容易想到的办法就是遍历，每次都将当前元素和下一个元素相比，如果后一个小于前一个，则说明后一个元素为原数组的最小元素。

代码为：

int result = nums[0];
for (int i = 0; i < nums.length - 1; i++) {if (nums[i + 1] < nums[i]) {result = nums[i + 1];break;}
}
return result;

但在这种情况下，最坏情况可能需要遍历n次，即时间复杂度为$O(n)$，而题目要求为$O(logn)$

其实看到 $O(logn)$ 基本可以知道思路为二分法

基本思路是：

• 每次定义数组的左右边界left和right，初始化为0和num.length-1
• 然后每次循环都取出中间元素，并将中间元素和左边界元素比较
• 如果大于等于说明左边都是非递减序列，那么要找的最小值肯定在中间和右边界之间
• 相反如果小于则说明最小值肯定在左边界和中间之间

例：

假设输入为[3,4,5,1,2]，初始化left=0，right=4，则mid=2此时nums[0]<nums[2]，所以更新left为2，更新后的mid为3，此时nums[2]>nums[3]，说明找到了最小元素，输出即可

一开始我写的是：

if (nums.length == 0) {return 0;
}
int left = 0;
int right = nums.length - 1;
while (left < right - 1) {int mid = (left + right) / 2;if (nums[mid] >= nums[left]) {left = mid;} else if (nums[mid] <= nums[right]) {right = mid;}
}
return nums[right];

但是当遇到某些特殊的输入值时结果不正确，比如[1,0,1,1,1]

然后后面修改了很多但一直没过，直到看到别人的解法才发现自己陷入了老是将中间值和左右值比较，但实际上只需将中间值和最右值比较即可，只有三种情况：

• 中间值小于最右值：说明右半边是非递减序列，则最小值应该在左半边
• 中间值大于最右值：说明右半边不是非递减序列，则最小值应该在右半边
• 如果等于，则说明无法判断，应该将right往左移

if (nums.length == 0) {return 0;
}
int left = 0;
int right = nums.length - 1;
while (left < right) {int mid = left + (right - left) / 2;if (nums[mid] > nums[right]) {left = mid + 1;} else if (nums[mid] < nums[right]) {right = mid;} else {right--;}
}
return nums[left];

这里 left=mid+1 的原因是因为 nums[mid] > nums[right]，则说明 num[mid] 肯定不是最小的，所以左边界应该在其 mid 的下一位

举个例子，比如输入为[3,4,5,1,2]，此时 nums[mid]=5 ，nums[right]=2 ，并且 nums[mid] > nums[right]，那么 nums[mid] 肯定不会是最小的，需要往右移一位。

同理，right = mid 的原因是因为对于下面这种输入时 [4,5,1,2,3]，此时 nums[mid]=1 ，nums[right]=3 ，并且 nums[mid] < nums[right]，如果说是right = mid - 1 的话会导致 mid 值没判断是不是最小的，可能会错过最终结果

完整代码

import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param nums int整型一维数组* @return int整型*/public int minNumberInRotateArray (int[] nums) {// write code hereif (nums.length == 0) {return 0;}int left = 0;int right = nums.length - 1;while (left < right) {int mid = left + (right - left) / 2;if (nums[mid] > nums[right]) {left = mid + 1;} else if (nums[mid] < nums[right]) {right = mid;} else {right--;}}return nums[left];}
}