剑指Offer #01 二维数组中的查找（Java描述）

╰+哭是因爲堅強的太久メ 2023-07-07 12:51 78阅读 0赞

> 题目来源：牛客网-剑指Offer专题  
> 题目地址：[二维数组中的查找][Link 1]

### 题目描述 ###

在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

### 题目解析 ###

**方法一：**  
暴力法，**遍历二维数组**，时间复杂度为  O ( n 2 ) O(n^2) O(n2)

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

**方法二：**  
根据题目信息可以知道，每一行的数字都是有序的。于是，我们**对每一行都进行二分查找**，时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn)

public class Solution { 
        public boolean Find(int target, int [][] array) { 
            for (int i = 0; i < array.length; i++){ 
            	//注意搜索的边界
                int left = 0, right = array[i].length - 1;
                while (left <= right) { 
                    int mid = (left + right) / 2;
                    if (array[i][mid] > target) { 
                        right = mid - 1;
                    } else if (array[i][mid] < target) { 
                        left = mid + 1;
                    } else { 
                        return true;
                    }
                }
            }
            return false;
        }
    }

**方法三：**  
由于在数组在水平和垂直方向都是递增的，所以我们可以从左下角开始，若当前值  n o w now now 比目标值  t a r g e t target target 大，则向上移动；若  n o w < t a r g e t now <target now<target ，则向右移动。以这种方法去搜寻目标值，时间复杂度 O ( n ) O(n) O(n)  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI5MjIyOQ_size_16_color_FFFFFF_t_70]

public class Solution { 
        public boolean Find(int target, int [][] array) { 
            int row = array.length - 1, col = 0;
            while (row >= 0 && col < array[row].length) { 
                if (array[row][col] > target) { 
                    row--;
                } else if (array[row][col] < target) { 
                    col++;
                } else { 
                    return true;
                }
            }
            return false;
        }
    }

--------------------

如果本文对你有所帮助，别忘了点赞哦~

[Link 1]: https://www.nowcoder.com/practice/abc3fe2ce8e146608e868a70efebf62e?tpId=13&tqId=11154&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI5MjIyOQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200223230509581.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI5MjIyOQ==,size_16,color_FFFFFF,t_70