【剑指offer】06 旋转数组的最小数字

题目描述

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。
NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 64M，其他语言128M

题目示例

输入：

[3,4,5,1,2]

返回值：

解法分析

先说明一下定义，非递减意为a[i]<=a[i+1]，递减意为a[i]>a[i+1]，非递增意为a[i]>=a[i+1]，递增意为a[i]<a[i+1]，因此非递减排序的数组类似[1,2,3,4,4,5,6,6]这种。

而旋转后的非递减排序的数组，形如[4,4,5,6,6,1,2,3]，可看出分为了左右两部分，而右侧（尾部）部分的最左侧元素即为数组中的最小数。因此我们只需要对比相邻两元素的大小，一旦满足a[i]>a[i+1]，即左侧元素大于右侧元素，a[i+1]就是数组中的最小值。

然而这种方式过于简单，并且时间复杂度为O(n)，更好的方法应该是使用二分法，可将时间复杂度降为O(logn)。

代码

 1 function minNumberInRotateArray(rotateArray)
 2 {
 3     // write code here
 4     if(rotateArray.length===0){
 5         return 0
 6     }
 7     var fir = 0;
 8     var las = rotateArray.length - 1;
 9     while(las - fir > 1){
10         var mid = Math.floor((fir+las)/2);
11         if(rotateArray[mid] < rotateArray[las]){
12             las = mid;
13         }else{
14             fir = mid
15         }
16     }
17     return Math.min(rotateArray[fir],rotateArray[las]);
18 }

执行结果