必会算法：在旋转有序的数组中找最小值

大家好，我是戴先生 今天给大家介绍一下如何利用玄学二分法找出最小值 想直奔主题的可直接看思路2 这次的内容跟 必会算法：在旋转有序的数组中搜索 有类似的地方 都是针对旋转数据的操作 可以放在一块来学习理解 ##题目 整数数组 nums 按升序排列，数组中的值互不相同 在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数） 例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 关于这段描述还有另外一种容易理解的说法： 将数组第一个元素挪到最后的操作，称之为一次旋转 现将nums进行了若干次旋转 找到数组中的最小值，并返回结果

##题解

###思路1

简单粗暴：遍历

就不多介绍了，大家都懂

时间复杂度：O(n)

空间复杂度：O(1)

###代码实现1

思路1的代码实现如下

    /**
     * 暴力破解法
     *
     * @param num    给定的旋转后数组
     * @return 查询结果
     */
    public static int findMin(int[] num) {
        if (num == null || num.length == 0) {
            return -1;
        }
        int min = num[0];
        for (int i = 0; i < num.length; i++) {
            if (num[i] < min) {
                min = num[i];
            }
        }
        return min;
    }

###思路2

还是那句话

凡是看到有序或者局部有序的数组查找问题

第一个想到的就应该是用二分法试试

下面我们来分析一下

一个增序的数组是这样的

旋转n次之后就是这样的

所以我们的目标就是在这样的数组里边找目标值

可以非常清晰的看到

第二段的所有值都是小于第一段的值

所以最小值就是在二段的第一个元素

还有一种极端的情况就是

经过多次旋转之后

数组又变成了一个单调递增的数组

此时的最小值就是第一个元素

我们用数组[1,2,3,4,5,6,7,8,9]举例说明

3次旋转之后是这个样子

此时我们还不知道这个数组是分了两段

还是单调递增的

使用二分查找的话，首先还是先找到中位数

start=0，nums[start]=4

end=8，nums[end]=3

mid为(0+8)/2=4，nums[mid]=8

此时nums[mid]>nums[start]

说明mid在第一段区间（或者整个数据都是单调递增的）

同时nums[mid]>nums[end]

由此可知：最小值存在于mid~end之间

接下来就是对mid~end之间的内容再次进行二分查找

start=4，nums[start]=8 start=8，nums[end]=3 mid=6，nums[mid]=1

此时nums[mid]<nums[start]

说明mid在第二段区间（或者整个数据都是单调递增的）

end必然也是在第二段区间（或者整个数据都是单调递增的）

所以可以判断出最小值必然存在第二段

也就是最小值存在于mid~end之间

此时问题就简化为了在一个单调递增的区间中查找最小值了

所以总的规律就是：

在二分法的基础上

当中间值mid比起始值start对应的数据大时

判断一下mid和end对应值的大小 nums[end]<=nums[mid]，则最小值在mid后边，start=mid nums[end]>nums[mid]，则最小值在mid前边，end=mid

###代码实现2 套用二分查找的通用公式

思路2的代码实现如下

    public static int findMin(int[] num) {
        if (num == null || num.length == 0) {
            return -1;
        }
        int start = 0;
        int end = num.length - 1;
        int mid;
        while (start + 1 < end) {
            mid = start + (end - start) / 2;
            if (num[mid] >= num[start]) {
                if (num[end] <= num[mid]) {
                    start = mid;
                } else {
                    end = mid;
                }
            } else {
                end = mid;
            }
        }
        return Math.min(num[start], num[end]);
    }

时间复杂度：O(logn)

空间复杂度：O(1)

##测试验证

文/戴先生@2022年07月09日