剑指offer—旋转数组的最小数字 解答

剑指offer—旋转数组的最小数字

题目描述

把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。
输入一个非递减排序的数组的一个旋转,输出旋转数组的最小元素。
例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。
NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。

示例 1:

输入: [3,4,5,1,2]
输出: 1

示例 2:

输入: [4,5,6,7,0,1,2]
输出: 0

思路

  • 二分查找法

非递减数组旋转后可以根据数组最小值把数组分为左右两个非递减数组,并且左边元素比右边大

数组中点与右边high元素进行比较,如果大于high,说明中点属于左边的非递减数组,最小值则在中点右边;如果小于high说明中点属于右边的非递减数组,最小值可能在左边或者中点处;如果相等则无法判断,可能在左边或者右边,需要对high进行减一再循环

代码

class Solution {
    public int findMin(int[] array) {
        if(array.length == 0){
            return 0;
        }
        int low = 0;int high = array.length-1;
        while(low<high){
            int mid = low + high >> 1;
            if(array[mid]>array[high]){
                low = mid + 1;
            }else if(array[mid]<array[high]){
                high = mid;
            }else{
                high = high - 1;
            }
        }
        return array[low];
    }
}