剑指Offer-旋转数组的最小值

发表于 | 阅读次数 | 阅读数

旋转数组的最小值

题目

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

思路

1.遍历数组找到最小值（面试官估计会说买橘子去，你再看看）
2.找到分界点
3.二分查找

代码

方法一就不上了，面试官会赶人吧.
 /**
 * 直接找分界点
 * @param array
 * @return
 */
public int minNumberInRotateArray(int[] array){
    for (int i=0;i<array.length;i++){
        if (array[i+1]<array[i]){
            return array[i+1];
        }
    }
    return 0;
}

/**
 * 二分法
 * @param array
 * @return
 */
public int minNumberInRotateArray_iii(int[] array){
    if (array.length==0){
        return 0;
    }

    int left = 0;
    int right = array.length-1;
    int middle = -1;
    while (array[left]>=array[right]){
        if (right-left==1){
            middle = right;
            break;
        }

        middle = left + (right-left)/2;
        if (array[middle]>=array[left]){
            left = middle;
        }

        if (array[middle]<=array[right]){
            middle = right;
        }
    }
    return array[middle];
}
0%