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

叁歲伎倆 2023-07-20 05:56 66阅读 0赞

![在这里插入图片描述][20200331204104596.gif_pic_center]

### 文章目录 ###

*  图解LeetCode刷题计划
 *   *  1、写在前面
     *  2、题目
     *  3、正文
     *  4、代码
     *  5、讨论

# 图解LeetCode刷题计划 #

## 1、写在前面 ##

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

距离秋招还有：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70_pic_center]  
希望能多刷点题，今天是第一期，争取每天一期，最多两天，欢迎大家监督我。。。公众号监督最好！！！

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70_pic_center 1]  
今天要讲解的题目是LeetCode153题，一道经典的面试题，旋转的排序数组。

![在这里插入图片描述][20200331223510788.png]

## 2、题目 ##

首先看一下题目，  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70]  
从题目给出的信息中，可以获取到的信息有两点：

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

你可能首先想到的是排个序，然后取个 `nums[0]`。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 1]  
哈哈，我估计面试官直接就让你 `out` 了，这种搜索类题目最好还是用二分法！

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

![在这里插入图片描述][20200331223457291.png]

## 3、正文 ##

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

> 蓝色是目标，绿色是mid  
> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70_pic_center 2]  
> 然后旋转了，极端情况有两种，分别是最大值在最左侧和最小值在最右侧的情况。

正常情况就很多种了。

根据二分法，先找到 `mid`，然后向目标移动，比如下图的第一个就是 `mid` 向 `right` 移动，第二个就是 `mid` 向 `left` 移动。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70_pic_center 3]  
**为什么是这样的呢？**

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

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

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

![在这里插入图片描述][20200331223448439.png]

## 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];
    }

![在这里插入图片描述][20200331155531886.png]

## 5、讨论 ##

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

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70_pic_center 4]  
即：

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

![在这里插入图片描述][2020033119171520.png]

> **如果有幸帮到你，请帮我点个【赞】，给个【关注】！如果能顺带【评论】给个鼓励，我将不胜感激。**

***如果想要更多的资源，欢迎关注 @我是管小亮，文字强迫症MAX~***

***回复【数据结构】即可获取我为你准备的大礼***

***想看更多文（段）章（子），欢迎关注微信公众号「程序员管小亮」~***

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70_pic_center 5]

[20200331204104596.gif_pic_center]: /images/20230528/5c32dc92bb8f4cc48a16205837a057b0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70_pic_center]: /images/20230528/a6757b9830dc42938c466f6078ab43be.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20230528/b08727dbea78409dbd9fa0844c8f59b4.png
[20200331223510788.png]: /images/20230528/edc12a9f874a4992bca4d42a2abb876d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70]: /images/20230528/0ddbc8be50314839b40d9363c28e797a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 1]: /images/20230528/e840114fed8d4f4c9e30c48470d28e96.png
[20200331223457291.png]: /images/20230528/ab6bc6eb1ebc432a9408d7153493b4a7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20230528/c1567e9f1e5243518d3d0eaa02b7f0cb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20230528/0c46ad2877344e4a9873977f2c0ddda8.png
[20200331223448439.png]: /images/20230528/1f2245e64fc740f0a75da9d2febed117.png
[20200331155531886.png]: /images/20230528/f475bad2cb94419280b97e7cf51e9dff.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20230528/c6da67e581de47e99d1dde95582c66b4.png
[2020033119171520.png]: /images/20230528/852ab3511c4f42078e9a7f1d956a93c6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20230528/6da1af03814c48dd959a7cdd62900274.png