【手绘漫画】图解LeetCode之寻找旋转排序数组中的最小值（LeetCode153题）

文章首发于本人CSDN账号:https://blog.csdn.net/tefuirnever

由于微信不允许外部链接，你需要点击页尾左下角的“阅读原文”，才能访问文中的链接。

1、前言

手绘漫画系列正式上线！！！"图解LeetCode刷题计划" 来了！！！

距离秋招还有：

希望能多刷点题，今天是第一期，争取每天一期，最多两天，欢迎大家监督我。。。公众号监督最好！！！

今天要讲解的题目是LeetCode153题，一道经典的面试题，旋转的排序数组。

2、题目

首先看一下题目，

从题目给出的信息中，可以获取到的信息有两点：

1. 数组是排序的；
2. 数组经过了旋转；

你可能首先想到的是排个序，然后取个 nums[0]。

哈哈，我估计面试官直接就让你 out 了，这种搜索类题目最好还是用二分法！

二分法查找，也称为折半法，是一种在有序数组中查找特定元素的搜索算法。

3、正文

首先分析一下情况，一个排序的数组，即原题给出的，0，1，2，4，5，6，7，这没有问题吧。

蓝色是目标，绿色是mid

然后旋转了，极端情况有两种，分别是最大值在最左侧和最小值在最右侧的情况。

正常情况就很多种了。

根据二分法，先找到 mid，然后向目标移动，比如下图的第一个就是 mid 向 right 移动，第二个就是 mid 向 left 移动。

为什么是这样的呢？

首先，取一个标志，假设取 right 元素，因为最小值偏向左侧。

因为数组本身带有顺序的原因：

• 如果 mid 元素大于 right 元素，那么说明右侧有小值，而我们寻找的最小值必然也在右侧；
• 如果 mid 元素小于 right 元素，那么说明右侧是大值，左侧是小值，我们寻找的最小值必然也在左侧；

4、代码

int findMin(int* nums, int numsSize){
    int left=0;int right=numsSize-1;
    while(right>left){
        int mid=left+(right-left)/2;
        if(nums[mid]>nums[right]){
            left=mid+1;
        }
        else{
            right=mid;
        }
    }
    return nums[left];
}

5、讨论

提个问题，为什么 left 是 mid+1，而 right 却是 mid？

其实这个问题是我自己比较疑惑的一个点，不过我觉得应该是这样的，因为 mid 更偏向于 left，而不是 right，证明如下，所以，left 是不用担心会错失的问题的，但是 right 却容易错失！！！

即：

• 明确 nums[mid]>nums[right]，最小值在右半边，收缩左边界，因为中值肯定不是最小值，左边界可以跨过 mid；
• 明确 nums[mid]<nums[right]，最小值在左半边，收缩右边界，因为中值也可能是最小值，右边界只能取到 mid；