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

发表于 | 分类于

前言

　　这道题找数组中的最小数字，类似的题目之前蘑菇街视频面试都考过，找数组中的最大的两个值或者三个值。直观解题方法就是循环一遍数组，这样的复杂度是O（n），但是由题目可知，数组已部分排序，我们利用二分查找的方法是可以减少我们的复杂度的，达到O（log n）。

旋转数组的最小数字

题目

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

分析

       二分查找法的核心思想就是：每次查找都可以排除不需要查找的一半，这道题我们是可以利用这个思想的。

       我们定义两个标志，初识是分别指向第一位和最后一位，按照题目的旋转规则，我们找到数组中间的元素，如果中间的元素位于前面的递增数组中，那他应该小于等于第二个个标志指向的元素，此时数组中最小的元素应该位于该中间元素的后面，排除了一半，利用了二分的思想；同样，如果中间元素位于后面递增子数组中，那么它应该大于等于第二个标志指向的元素。如果相等，把最高位往前移一位，最后第一个标志上就是最小值。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public class minNumberInRotateArray_6 {
    public int minNumberInRotateArray(int [] array) {
        //定义两个标志指向首位索引
        int low = 0 ; int high = array.length - 1;
        //结束条件
        while(low < high){
            //取中间元素
            int mid = low + (high - low) / 2;
            //中间元素比尾数大，最小值在后半段
            if(array[mid] > array[high]){
                low = mid + 1;
            }
            //如果相等，高位减1
            else if(array[mid] == array[high]){
                high = high - 1;
            }
            //如果中间元素比尾数小，最小值在前半段
            else{
                high = mid;
            }
        }
        //循环结束，低位标志就是最小值所在
        return array[low];
    }
}