剑指offer-二维数组中的查找

文章目录

- - - 题目描述
    - 题解一无脑暴力循环
    - 题解二初始二分法

🌕博客x主页：己不由心王道长🌕!
🌎文章说明：剑指offer-二维数组中的查找🌎
✅系列专栏：剑指offer
🌴本篇内容：对剑指offer中的数组进行学习和解析🌴
☕️每日一语：这个世界本来就不完美，如果我们再不接受不完美的自己，那我们要怎么活。☕️
🚩 交流社区：己不由心王道长(优质编程社区)

题目描述

在一个 n * m 的二维数组中，每一行都按照从左到右非递减的顺序排序，每一列都按照从上到下非递减的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

示例:

现有矩阵 matrix 如下：

[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
给定 target = 5，返回 true。

给定 target = 20，返回 false。

限制：

0 <= n <= 1000

0 <= m <= 1000

题解一无脑暴力循环

思路：
由于题目给出的是一个n * m 的二维数组，不考虑其他因素，只要判断数组里面有没有目标元素而言，直接双层for循环暴力解决，代码如下：

class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
       for(int i=0;i<matrix.length;i++){
           for(int j= 0;j<matrix[i].length;j++){
               if(matrix[i][j]==target){
                   return true;
               }
           }
       }return false;
    }
}

结果:
在这里插入图片描述
想法：确实无脑暴力可解，但是这里的执行用时感觉不对劲，两层for循环，时间复杂度O(n*m),应该不算快才对。

题解二初始二分法

思路：
在这里插入图片描述
如图所示，题目给出的是没一行都按照从左到右非递减的顺序排列，就是说其实这个数组在一维的角度来说是有顺序的，当然二维也有，仔细观察就能发现————用处就是，我们的二分法在应用的时候就需要有顺序的数组，明白了吗？
先看代码：

class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
       
       for(int i =0;i<matrix.length;i++){
       int left=0;//在while循环外侧设置，当while循环结束后可以重新给left和right赋值
       int right=matrix[0].length-1;//开始是在matrix[0][x]使用二分法，就是每一行使用二分，一行结束之后换到下一行
       while(left<=right){
           int middle = left+((right-left)/2);
           if(matrix[i][middle]==target){
               return true;
           }else if(target<matrix[i][middle]){
               //目标小，向左查找
               right=middle-1;
           }else{
               left = middle+1;
           }

       }}
       return false;

    }
}