描述

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

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

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

import java.util.ArrayList;
public class Solution {//这题仔细观察发现：本身是非递减的数组，你将前面的若干个数字进行旋转，整个数组被分为两部分//第一部分和第二部分都是非递减的，但是前面整体比后面大//那么最小的数字肯定在第二部分的第一个，如果去找到第二部分的头，是我们要做的//这题有多种解法，但是利用二分和上面的查找思想是比较好的public static int minNumberInRotateArray(int[] array) {if (array == null || array.length == 0) {return 0;}int i = 0;int j = array.length - 1;int mid = 0;while (i < j) {if (j - i == 1) {mid = j;break;}if (array[j] == array[j] && array[mid] == array[i]) {int minnum = array[i];for (int k = i + 1; k < j; k++) {if (array[k] < minnum) {minnum = array[k];}}return minnum;}mid = i + ((j - i)>>1);if (array[mid] >= array[i]) {//说明此时中间下标还是处于第一部分i = mid;}if (array[mid] < array[i]) {//此时mid处于第二部分j = mid;}}return array[mid];}
}