题目描述
把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。
输入一个非递减排序的数组的一个旋转,输出旋转数组的最小元素。
NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。
示例1
输入
[3,4,5,1,2]
返回值
1
解题思路
二分法适用于有序数组(如非递减)
而旋转数组的区别在于有一部分的旋转,相当于部分有序,而且旋转过去的比前半段小
特殊情况分析
特殊情况一:数组大小为0,则返回0
特殊情况二:如果完全旋转,则数组还是非递减数组,则最小值为第一个数
一般情况分析:
利用二分法去left=0;right=length-1;mid=left+(right-left)/2;
array[mid]>array[right]======则证明最小值在右半段,如【3,4,5,1,2】中5>2;则应该令left=mid+1;
array[mid]<array[right]======则证明最小值在左半段,如【3,1,2,3,4】中2<4;由于mid是比最右边的数小,只能证明最小值不在mid右侧,mid处也可能刚好是最小值,所以应令right=mid;
array[mid]=array[right]======这种情况对应于数组中有好多个一样的数字,如【1,1,1,1,0,1,1,1】只能依次减一,直到没有重复元素
易错点记录
left=0;right=length-1;mid=left+(right-left)/2
求中间值,求左加上左右间隔的一半作为中间值
java代码

import java.util.ArrayList;
public class Solution {
     public int minNumberInRotateArray(int [] array){
         //运行时间:203ms  占用内存:28660k
        int length=array.length;
        if(length==0){
            return 0;
        }
        int left=0;
        int right=length-1;
        while(left<right){
            if(array[left]<array[right]){
                return array[left];
            }
            int mid=left+(right-left)/2;
            if(array[mid]>array[right]){
                left=mid+1;
            }
            else if(array[mid]<array[right]){
                right=mid;
            }
            else{
                left++;
            }
        }
        return array[left];
    }
}