LeetCode 240. 搜索二维矩阵 II（二维二分）_leetcode240

题目描述：给定一个矩阵，矩阵的每一行，从左到右是是升序排列；矩阵的每一列，从上到下是升序排列。

思路：一看到在有序的数中搜索某个目标值，立刻想到二分。但是和普通的二分不同，这道题是二维的二分。

观察规律：对于点 [x,y]，这个位置的数a，是矩阵左上角到[x,y]这个区域内的最大的值；是[x,y]到矩阵右下角这个区域内最小的值。

我们每次比较[x,y]位置上的数a，与目标值target的大小。如果a < target，而由于a是左上角到[x,y]中最大的数，那么整个左上角区域的数，都是小于target的，那么可以排除掉左上角部分的区域；同理，如果a > target，由于a是[x,y]到右下角中最小的数，则可以排除掉右下角部分的区域。

完成区域排除后，对剩下的区域，划分为2个矩形，递归的进行搜索即可。

图示如下，

• 若a < target，则排除掉左上角区域，递归的搜索A，B两个矩形区域
  
• 若a > target，则排除掉右下角区域，递归的搜索A，B两个区域
  

所以，我们编写一个递归函数，搜索指定矩形区域即可（指定矩形的左上角坐标和右下角坐标即可）。

/***
* (li, lj) 左上角坐标
* (ri, rj) 右下角坐标
*/
public boolean binarySearch(int[][] matrix, int li, int lj, int ri, int rj, int target);
1
2
3
4
5

算法流程的伪代码如下

# 对左上角点与右下角点围起来的矩形区域, 进行搜索

search(左上角点, 右下角点, 目标值):
   if(左上角点 右下角点 无法构成一个矩形) return false
   if(左上角点 右下角点 是同一个点) return 当前位置的值 == 目标值
   计算矩阵中点的位置，设其值为a
   if (a == 目标值) return true
   if (a < 目标值) :  
       排除左上角区域, 将剩余区域划分为A，B两个矩形，两个矩形中的任意一个能搜到即可
       return search(A) || search(B)
   if (a > 目标值) :
       排除右下角区域，将剩余区域划分为A,B两个矩形，两个矩形中的任意一个能搜到即可
       return search(A) || search(B)
   
1
2
3
4
5
6
7
8
9
10
11
12
13
14

Java代码

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int n = matrix.length;
        int m = matrix[0].length;
        // 二维二分
        return binarySearch(matrix, target, 0, 0, n - 1, m - 1);
    }

    
    private boolean binarySearch(int[][] matrix, int target, int li, int lj, int ri, int rj) {
        if (li > ri || lj > rj) return false; // 没有可搜索的地方了
        if (li == ri && lj == rj) return target == matrix[li][lj]; // 最后一个格子
        // 获取中点
        int mi = li + ri >> 1;
        int mj = lj + rj >> 1;
        if (target == matrix[mi][mj]) return true; // 找到了提前返回
        if (target > matrix[mi][mj]) {
            // 中点的位置比 target 小, 递归地搜索剩余的两块区域
            return binarySearch(matrix, target, mi + 1, lj, ri, rj) || binarySearch(matrix, target, li, mj + 1, mi, rj);
        } else {
            // 中点的位置比 target 大, 递归地搜索剩余的两块区域
            return binarySearch(matrix, target, li, lj, mi - 1, rj) || binarySearch(matrix, target, mi, lj, ri, mj - 1);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

上面的整个算法过程，是比较典型的二分的做法（每次排除掉一个矩形区域）。

下面还有一种很巧妙的方法，Z字形搜索。我们考虑从矩形的四个顶点出发，进行搜索。

比如从左上角顶点出发，我们的搜索过程应该是每一步只能往右或往下走；从左下角顶点出发，每一步应该只能往右或往上走；从右上角，每一步只能往左或往下走；从右下角，每一步只能往左或往上走。

我们发现，当从右上角，或左下角出发，进行搜索时。每走一步都具有二相性。什么意思呢？比如从右上角，往左走，数字一定变小，往下走，数字一定变大；从左下角，往右走，数字一定变大，往上走，数字一定变小。

这就有点类似二叉排序树了，在二叉排序树的每个节点，往左走是变小，往右走是变大。我们可以将二叉排序树和这道题联系起来。

假设从右上角顶点出发，设当前位置值为a，若a < target，则往下走，排除掉当前位置所在的这一行（这一行全都比a小）；若a > target，则往左走，排除掉当前位置所在的这一列（这一列全都比a大）。
并且走的过程中是不可能走回头路的。什么意思呢？假设当前已经走到了点[x,y]，这个位置了，那么目标值只可能落在矩形的左下角，到[x,y]这个区域内，其他的区域全部在走的过程中被排除掉了（只需要继续用当前位置的值和目标值进行比较，并往左或往下走即可，不用回头）。（自行想象一下这个过程，下图阴影区域的上方横着的部分的左侧都是比目标值小的，竖着部分的下侧都是比目标值大的，横竖交叉的那个小方块中，可能比目标值大也可能比目标值小）

这个特性（二相性）只有在从右上角出发，或者从左下角出发时，才能满足。

那么搜索过程中，走过的位置，连起来就像是在走Z字形。假设矩形共有n行，m列，则最多只会走m + n次。因为每走一次都会排除掉一行或者一列。

Java代码：

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int n = matrix.length, m = matrix[0].length;
        int i = 0, j = m - 1; // 从右上角开始走
        while(i < n && j >= 0) { // 最多会走到左下角去
            int a = matrix[i][j];
            if (a == target) return true;
            if (a < target) i++; // 排除掉当前这一行, 往下走
            else j--; // 排除掉当前这一列, 往左走
        }
        return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

半个多月没刷leetcode了，昨天这道题，读完题目后我立刻想到了二分，但是对于具体的细节，则想了半天，包括找到某个点是左上角的最大值，右下角的最小值这种规律。我一开始想的是，从第一行出发，先在行内进行二分，找到最终的位置，再在这个位置所在的列上，进行二分，找到最终位置，再按行进行二分。但这种思路的代码实现并不是很好做。后来想到以整个矩形进行二分，每次二分出一块矩形区域，再后来想到递归对剩余的区域进行操作。比较关键的点在于，对剩余区域的划分，以及确定这些区域的边界点。
好在，这道题我昨天虽然花了40分钟，但是没看题解自己做出来了，还是一次AC，挺开心的。哈哈哈哈！（虽然代码写的挺长，第一版的代码对只剩一行和只剩一列的情况做了特判，后来发现不用加这个特判（虽然加了后性能会略微提升一些）