剑指 offer 第一题：二维数组中的查找

╰+攻爆jí腚メ 2022-03-16 02:04 165阅读 0赞

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg]

### 题目描述 ###

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

### 题目分析 ###

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 1] 图 1

如果没有头绪的话，很显然使用 **暴力解法** 是完全可以解决该问题的。

即遍历二维数组中的每一个元素，时间复杂度：O(n^2)。

其实到这里我们就可以发现，使用这种暴力解法并没有充分利用题目给出的信息。这个二维数组是有特点的。

*  每一行都是**递增**的
 *  每一列都是**递增**的

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 2] 图 2

### 解法 ###

### 解法一：二分法 ###

对于有序数组的查找问题而言，**二分法**是最容易想到的一个解法。

在这里，对每一行使用二分查找，时间复杂度为 O(nlogn) 。二分查找复杂度 O(logn)，一共 n 行，所以是总体的时间复杂度是 O(nlogn) 。

### 解法二：规律法 ###

根据二维数组由上到下，由左到右递增的规律。

从左下角开始遍历，如果当前值比 target 小则往右找，如果比 target 大则往上找，如果存在，必然可以找到目标数字。

即选取右上角或者左下角的元素 a\[row\] \[col\] 与 target 进行比较， 当target小于元素 a\[row\] \[col\] 时，那么 target 必定在元素 a 所在行的左边,让 col-- ；当 target 大于元素 a\[row\] \[col\] 时，那么 target 必定在元素 a 所在列的下边,让 row++ ；

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 3] 图 3

代码如下：

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

### 解法三：二分规律法 ###

将解法一和解法二进行结合：**对每行每列都使用二分查找，此时的时间复杂度为 O(logn \* logm)**。

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 4] 图 4

比如查找数字 9，首先使用用二分查找选出一行，总共有 5 行，那么`( 0 + 5 ) / 2 = 2`，所以我们找出了第 2行为基准行。

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 5] 图 5

接下来对这一行（即第 2 行）又使用二分查找， 找出这一行（即第 2 行）中最后一个比目标值小的值，这里是 6。

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 6] 图 6

**6** 及其所在的行和列把这个矩形划分为 **4** 部分：

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 7] 图 7

1.  **左上部分（图 7 灰色部分）**，包括所在行的左边部分和所在列的上边部分：这一部分是绝对不会有目标数字的。因为这部分数字肯定比 6 小，而 6 又是小于目标数字的，所以左上部分全部小于目标数字。也就是说这个区域的数字不需要再进行判断了。
2.  **右下部分（图 7 绿色部分）**，包括所在行的右边部分，但不包括所在列的下面部分， 这一部分也是绝对不会有目标数字的。因为这部分都比 6 右边的数字 11 大，而 11 又比目标数字 9 更大，所以右下部分全部都比目标数字大。也就是说这个区域的数字也不需要再进行判断了。
3.  **左下部分（图 7 蓝色部分）**，可能含有目标数字。
4.  **右上部分（图 7 棕色部分）**，可能含有目标数字。

这样，实际上筛选的区域就只剩下**左下部分（图 7 蓝色部分）**和 **右上部分（图 7 棕色部分）**这两块区域了，相比于解法二而言，使用这种解法**平均情况下每一次查找，都可以把行和列的长度减少一半**。

代码如下：

public class Solution {
        
           public boolean Find(int target, int [][] array) {
        
           // 特殊情况处理
           if (array == null || array.length == 0 || array[0].length == 0) {
        
                return false;
            }
    
            int h = array.length - 1;
            int w = array[0].length - 1;
    
            // 如果目标值小于最小值 或者 目标值大于最大值，那肯定不存在
            if (array[0][0] > target || array[h][w] < target) {
        
                return false;
            }
            return binarySearchIn2DArray(array, target, 0, h, 0, w);
        }
    
    
         public static boolean binarySearchIn2DArray(int[][] array, int target, int startX, int endX, int startY, int endY) {
        
            if (startX > endX || startY > endY) {
        
                return false;
            }
            //首先，根据二分法找出中间行
            int x = (startX + endX) / 2;
            //对该行进行二分查找
            int result = binarySearch(array[x], target, startY, endY);
            //找到的值位于 x 行，result 列
            if (array[x][result] == target) {
        
                return true; // 如果找到则成功
            }
            //对剩余的两部分分别进行递归查找
            return binarySearchIn2DArray(array, target, startX, x - 1, result + 1, endY)
                    || binarySearchIn2DArray(array, target, x + 1, endX, startY, result);
        }
    
         public static int binarySearch(int[] array, int target, int start, int end) {
        
            int i = (start + end) / 2;
            if (array[i] == target || start > end) { 
                return i;
            } else if (array[i] > target) {
        
                return binarySearch(array, target, start, i - 1);
            } else {
        
                return binarySearch(array, target, i + 1, end);
            }
        }
    }

### End ###

**今日问题：**

不知不觉「五分钟学算法」已更新了快百篇原创，坚持原创日更很长一段时间了。所以，你希望接下来小吴更新哪方面的算法知识内容呢？留言区点赞前五名的都可获得小红包一个，**小吴很期待你的建议**~

**打卡格式：**

打卡 X 天，答：xxx 。

[![640?wx\_fmt=png][640_wx_fmt_png]][640_wx_fmt_png_640_wx_fmt_png]

喜欢就点击“好看”吧！

[640_wx_fmt_jpeg]: /images/20220316/7caf8decc5fb455b8fcbcb8aef0e1ca5.png
[640_wx_fmt_jpeg 1]: /images/20220316/fc753121e79a464cbcd6067c4aa48795.png
[640_wx_fmt_jpeg 2]: /images/20220316/a1318da9a0b5482a9f9a6ceff7180857.png
[640_wx_fmt_jpeg 3]: /images/20220316/29bf1c56ca0148a9b7572694045bcdd5.png
[640_wx_fmt_jpeg 4]: /images/20220316/14b80e029c73445e90b9f7870d3b98c5.png
[640_wx_fmt_jpeg 5]: /images/20220316/68ace502626d40e79faea0239c479334.png
[640_wx_fmt_jpeg 6]: /images/20220316/b36b5d6d8718466ba6324cd72d4b6d76.png
[640_wx_fmt_jpeg 7]: /images/20220316/867c5088218542e8a5a86f917409b681.png
[640_wx_fmt_png]: https://img-blog.csdnimg.cn/img_convert/406f1d287e7f15f549343bc20aa29669.png
[640_wx_fmt_png_640_wx_fmt_png]: /images/20220316/5f62d3a46bd84f2b81f870040b5ecac0.png