【手绘漫画】图解LeetCode之搜索旋转排序数组（LeetCode33题），二分查找

末蓝、 2023-07-22 11:28 15阅读 0赞

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

### 文章目录 ###

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

# 图解LeetCode刷题计划 #

## 1、写在前面 ##

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

今天是第六期，争取每天一期，最多两天一期，欢迎大家监督我。。。  
![在这里插入图片描述][20200405221028705.png]  
目前的题目暂定  
![在这里插入图片描述][20200405221124509.png]  
一两个月必定开启剑指offer，敬请期待。

今日依旧还是是二分查找算法~  
![在这里插入图片描述][20200331223510788.png]

## 2、题目 ##

首先看一下题目，  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70]  
排序，旋转，不重复，没错，就是我，[【手绘漫画】图解LeetCode之寻找旋转排序数组中的最小值（LeetCode153题）][LeetCode_LeetCode153]大声喊到。  
![在这里插入图片描述][20200405221349674.jpeg]  
嘻嘻，不同之处是什么呢？就是153是最小值，而33则是目标值，当然题目的长度也是不一样的~  
![在这里插入图片描述][20200331223457291.png]  
![在这里插入图片描述][2020040522155962.png]

## 3、正文 ##

首先分析一下情况，

寻找的目标是 `target`，在这里是1，  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 1]  
开始二分法，

如何判断一个区间是不是递增或递减的，因为数组是排序的，所以只要比较两端点，如果左端点小于右端点，那么数组递增。  
![在这里插入图片描述][20200405225720223.png]  
好了，接着看。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 2]  
如果目标在两端点之间，那么就执行 `left=mid+1`。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 3]  
记得先判断，`nums[mid]` 和 `target` 是不是相等。

**复杂度：**

*  时间复杂度：和二分搜索一样，是  O ( log ⁡ n ) O(\\log n) O(logn)。
 *  空间复杂度： O ( 1 ) O(1) O(1)。

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

## 4、代码 ##

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

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

## 5、讨论 ##

最近在认真研究一个问题，当然不是谈婚论嫁，而是二分查找，二分查找算法的难度不大，但是细节多到爆炸，，，

*  比如 `为什么 while 循环的条件中是 <=，而不是 < ？`；
 *  再比如 `为什么 left = mid + 1，right = mid - 1？我看有的代码是 right = mid 或者 left = mid`；
 *  或者 `为啥好多的 mid = left + (right - left) / 2; 而不是 mid = (right + left) / 2;`

准备下期出个分析，看看能不能讲明白了。。。  
![在这里插入图片描述][2020033119171520.png]

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

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

[20200405220916386.gif_pic_center]: /images/20230528/6d5469020f5a46f2ace395d0023c5f3e.png
[20200405221028705.png]: /images/20230528/89382e0ddf2346efa1087b1ae04907bd.png
[20200405221124509.png]: /images/20230528/a1285d0ee35341708534c0115c78fc72.png
[20200331223510788.png]: /images/20230528/c43af0325316407ba63b0c631dd76633.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70]: /images/20230528/b456449332654afeb4a5f0a0bde90d38.png
[LeetCode_LeetCode153]: https://blog.csdn.net/TeFuirnever/article/details/105228617
[20200405221349674.jpeg]: /images/20230528/27329a6046b94c35abd3d49b69cc039d.png
[20200331223457291.png]: /images/20230528/37a39ed02b1b447193ea0a6164e34221.png
[2020040522155962.png]: /images/20230528/3403011715d34d30a1d4c1dbb2a33609.png?
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 1]: /images/20230528/883e05c6198d4a159b27d86851587e12.png
[20200405225720223.png]: /images/20230528/bca15a8fb61348dcb4d89db5552d5aff.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 2]: /images/20230528/5ad2b2cfa41749b6ad7de9f0baedb4fb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 3]: /images/20230528/e1ffecd60a5d49d19f5d5190322518c6.png
[20200331223448439.png]: /images/20230528/74b883f095654a79a73c06c3b8a42750.png
[20200405205540633.png]: /images/20230528/f969e09fdc34424eb85b1cdd2b499e13.png
[2020033119171520.png]: /images/20230528/a4d8f3c7fa6f45058deda80ab3ebf967.png