矩阵的二分查找！【手绘漫画】图解LeetCode之搜索二维矩阵（LeetCode 74）

深碍√TFBOYSˉ_ 2023-05-22 15:29 7阅读 0赞

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

### 文章目录 ###

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

# 图解LeetCode刷题计划 #

## 1、写在前面 ##

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

今天是第十五期，争取每天一期，最多两天一期，欢迎大家监督我。。。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70]

这一期是一个矩阵数组的二分查找！！！

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

## 2、题目 ##

首先看一下题目，

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 1]  
这里要先确定一个问题，每行的第一个整数大于前一行的最后一个整数！！！所以不要想得那么简单，但是也不难！  
![在这里插入图片描述][20200331223457291.png]

## 3、正文 ##

一起来看：

首先这个题比较难的应该就是数组和矩阵的转换问题了~公式比较固定，索引求商列数就是横坐标，索引求余列数就是纵坐标。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 2]  
转换成数组之后，就进行正常的二分查找就好了，模板之前讲过了，套用就完了。  
![在这里插入图片描述][20200331223448439.png]

## 4、代码 ##

class Solution { 
    public:
        bool searchMatrix(vector<vector<int>>& matrix, int target) { 
            if(matrix.empty()||matrix[0].empty()) return false;
    
            int m=matrix[0].size(),n=matrix.size();
            int left=0;
            int right=m*n-1;
            while(left<right){ 
                int mid=left+right>>1;
                if(matrix[mid/m][mid%m]>=target){ 
                    right=mid;
                }
                else{ 
                    left=mid+1;
                }
            }
            if(matrix[left/m][left%m]==target) return true;
            return false;
        }
    };

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

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

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

[2020041221504330.gif_pic_center]: /images/20230521/bc8aa9aa5afe497e9f3d5984eca79f62.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70]: /images/20230521/326ccc9f9c2f4cf28c45d00eb107649d.png
[20200331223510788.png]: /images/20230521/823208ccfcda4bb081a3f6f4653d17de.png
[2020040522155962.png]: /images/20230521/3bb93a791d2e4bf385ae47cf1a8f6142.png?
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 1]: /images/20230521/78d87d78aad04dcca08fba64bcb34df3.png
[20200331223457291.png]: /images/20230521/a4941f9b4847405c8be70469a6942341.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 2]: /images/20230521/d261fbb8401741a4b510c2f40d205ed8.png
[20200331223448439.png]: /images/20230521/0df6b2ca3e3945768d93c27ca5eb34cb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 3]: /images/20230521/40eeabfaf1a048dea5b67f72d6d54476.png
[2020033119171520.png]: /images/20230521/1ec2d252d95d470fb1c773774e3d13cf.png