从矩阵中查找数字是否存在

Dear 丶 2023-10-06 09:24 37阅读 0赞

题目：一个矩阵，从左往右依次增大，从上往下依次增大；  
在矩阵中查找，给定数字是否存在；

分析：从矩阵整体左往右看：在矩阵的最右边的一排，是各自一排中最大的，（灵魂画手来了）如图  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3NTUwOTg2_size_16_color_FFFFFF_t_70_pic_center]  
右上角的第一个点（称作A点吧），有一个性质，如果比A点大，那么在第一排肯定找不到该数字的只能往下一排找；如果比A小，只能往左边移动；在移动到下一个点时，依然可以用上面的思路继续判断；  
按照这个思路，最坏的结果，则是在矩阵的左下角：找到/没找到；  
那么，这个算法的边界也就好确定了；

```
    public boolean  find(int target ,int[][] a){
    
        int m = 0;
        int n = a[0].length-1;
        while(true){
            if(m >a.length-1 || n <0){//边界，
                return false;
            }
            if(target == a[m][n]){//找到了，直接返回
                return true;
            }
    
            if(target < a[m][n]){//左移
                n--;
                continue;
            }
    
            if(target > a[m][n]){//右移
                m++;
                continue;
            }
    
    
        }
    
    
    
    
    
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3NTUwOTg2_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20200524012118870.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3NTUwOTg2,size_16,color_FFFFFF,t_70#pic_center