74&240. 搜索二维矩阵（二分法）

74. 搜索二维矩阵

本题来自 LeetCode：74. 搜索二维矩阵^[1]

题目描述

编写一个高效的算法来判断 m x n矩阵中，是否存在一个目标值。该矩阵具有如下特性：
每行中的整数从左到右按升序排列。
每行的第一个整数大于前一行的最后一个整数。
示例  1:

输入:
matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
target = 3
输出: true

示例  2:

输入:
matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
target = 13
输出: false

两次二分查找

题目分析

由于每行从左至右递增、并且每行的第一个数大于前一行的最后一个数。因此目标值 target的位置是固定的。

可以先用二分查找，找到目标值`target`可能在哪一行上；

根据`步骤1`找到的可能的行，对该行再进行二分查找，从而判断是否存在目标值`target`；

题目解答

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        int m = matrix.length;
        int n = matrix[0].length;

        int top = 0;
        int bottom = m - 1;
        // 先对行进行二分查找，目的是找到target可能在哪一行上，
        // 若top = bottom，则直接进入下一个二分查找
        while(top  bottom) {
            // 中间行
            int mid = (top + bottom)  1;
            // 若mid行的最后一个元素小于target
            if(matrix[mid][n-1]  target) {
                top = mid + 1;
            // 若mid行的第一个元素大于target
            } else if(matrix[mid][0]  target) {
                bottom = mid - 1;
            // 若target位于mid行之间，则表示target可能位于mid行，则中止循环
            } else if(matrix[mid][0]  target &&  target  matrix[mid][n-1]){
                top = mid;
                bottom = mid;
                break;
            // 若mid行的第一个元素或者最后一个元素等于target
            } else {
                return true;
            }
        }
        // 对target可能存在的行进行二分查找
        // 当前行下标为为 top = bottom
        int left = 0;
        int right = n - 1;
        while(left = right) {
            int mid = (left + right)  1;
            if(matrix[top][mid] == target) {
                return true;
            } else if(matrix[top][mid]  target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return false;
    }
}

复杂度分析：
时间复杂度： O(log(m)) + O(log(n)) ，分别对长度为 m、 n的数组进行二分法查找
空间复杂度： O(1)

一次二分查找

题目分析

由于每行从左至右递增、并且每行的第一个数大于前一行的最后一个数。那么将该二维数组按顺序展开其实就是一个有序的一维数组`nums`，一维数组的区间范围为`[0, m * n - 1]`。

假设`nums[i]`为展开的一维数组的下标为`i`的值，那么对应到二维数组`matrix`的位置为`matrix[i / n][i % n]`。

因此可以通过二分查找这个一维数组`nums`，并将下标映射到二维数组上。

题目解答

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        int m = matrix.length;
        int n = matrix[0].length;

        // 对虚的一维数组进行二叉查找
        int left = 0;
        int right = m * n - 1;
        while(left = right) {
            int mid = (left + right)  1;
            // 映射到二维数组的位置
            int midNum = matrix[mid / n][mid % n];
            if(midNum == target) {
                return true;
            } else if(midNum  target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return false;
    }
}

复杂度分析：
时间复杂度： O(log(m * n)) ，对长度为 m * n的数组进行二分法查找
空间复杂度： O(1)

240. 搜索二维矩阵 II

本题来自 LeetCode：240. 搜索二维矩阵 II^[2]

题目描述

编写一个高效的算法来搜索 m x n矩阵 matrix中的一个目标值 target。该矩阵具有以下特性：
每行的元素从左到右升序排列。每列的元素从上到下升序排列。
示例:
现有矩阵 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。

m次二分查找

题目分析

由于每行从左至右递增、并且由上自下也是递增的。因此 target位置不是固定的，不能确定位于哪一行上，不能用 74.搜索二维矩阵的解法来解答。

由于每行还是从左至右递增的，因此可以先通过对每行来进行二分查找来解答；

若某一行找到目标值`target`，则表示矩阵中包含目标值；若都没有找到，则不包含目标值；

题目解答

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        int m = matrix.length;
        int n = matrix[0].length;

        // 对每一行进行二分法查找
        for(int i = 0; i  m; i ++) {
            if(binarySearch(matrix, i, n, target)) {
                return true;
            }
        }
        return false;
    }

    private boolean binarySearch(int[][] matrix, int row, int n, int target) {
        int left = 0;
        int right = n - 1;
        while(left = right) {
            int mid = (left + right)  1;
            if(matrix[row][mid] == target) {
                return true;
            } else if(matrix[row][mid]  target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return false;
    }
}

复杂度分析：
时间复杂度： O(mlog(n)) ， m次长度为 n的数组二分法查找
空间复杂度： O(1)

解法二

题目分析

可以观察到上面的解法，可能存在一些不必要的查找。题目给出的示例为例：

[
  [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时， 最后两行的查找是没有必要，因为这两行的首元素（该行最小值） 10、 18，大于目标值 5。这样就将搜索范围缩小到：

[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [-,   -,  -,  -,  -],
  [-,   -,  -,  -,  -]
]

综上，可以剪掉一些不必要的二分查找，剪枝规则为：行尾元素小于目标值 target，行首元素大于目标值 target。

题目解答

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        int m = matrix.length;
        int n = matrix[0].length;

        // 对每一行进行二分法查找
        for(int i = 0; i  m; i ++) {
            // 行尾元素小于目标值target，表示该行元素都小于target
            if(matrix[i][n - 1]  target) {
                continue;
            }
            // 行首元素大于目标值target，表示该行及之后所有行的元素都大于target。
            if(matrix[i][0]  target) {
                return false;
            }
            if(binarySearch(matrix, i, n, target)) {
                return true;
            }
        }
        return false;
    }

    private boolean binarySearch(int[][] matrix, int row, int n, int target) {
        int left = 0;
        int right = n - 1;
        while(left = right) {
            int mid = (left + right)  1;
            if(matrix[row][mid] == target) {
                return true;
            } else if(matrix[row][mid]  target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return false;
    }
}

复杂度分析：
时间复杂度： O(mlog(n)) ，时间复杂度和解法一一样，这里并没有降低复杂度
空间复杂度： O(1)

解法三

题目分析

接着 解法二的分析，继续优化。查找目标值 5，将搜索范围缩小到以下区间后，

[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [-,   -,  -,  -,  -],
  [-,   -,  -,  -,  -]
]

发现还是存在无效的查询，可以看到第一列的尾元素（该列最大值） 3小于目标值 5，后三列的首元素 7、 11、 15大于目标值 5。因此也没有比较查找这些区间。故将搜索范围继续缩小到以下区间：

[
  [-,   4,  -, -, -],
  [-,   5,  -, -, -],
  [-,   6,  -, -, -],
  [-,   -,  -, -, -],
  [-,   -,  -, -, -]
]

然后继续以 行为纬度来缩小范围至：

[
  [-,   -,  -, -, -],
  [-,   5,  -, -, -],
  [-,   -,  -, -, -],
  [-,   -,  -, -, -],
  [-,   -,  -, -, -]
]

最后得到结果。

采用四个变量记录查找范围。`matrix[top][left] ~ matrix[bottom][right]``top`：起始行； `bottom`：结束行； `left`：起始列； `right`：结束列；

分别对四条边进行二分法查找，不断缩小范围。

题目解答

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        int m = matrix.length;
        int n = matrix[0].length;

        int top = 0;
        int bottom = m - 1;
        int left = 0;
        int right = n - 1;
        int mid;
        while(top = bottom && left = right) {
            // 缩小左上角的范围
            while(top = bottom && matrix[top][right] = target) {
                if(matrix[top][right] == target) return true;
                top ++;
            }
            // 缩小右上角的范围
            while(top = bottom && matrix[bottom][left] = target) {
                if(matrix[bottom][left] == target) return true;
                bottom --;
            }
            // 缩小左下角的范围
            while(top = bottom && left = right && matrix[bottom][left] = target) {
                if(matrix[bottom][left] == target) return true;
                left ++;
            }
            // 缩小右下角的范围
            while(top = bottom && left = right && matrix[top][right] = target) {
                if(matrix[top][right] == target) return true;
                right --;
            }
        }
        return false;
    }
}

复杂度分析：
时间复杂度： O(m + n)， 这里我们最多只需要迭代长度分别为 m、 n的数组。
空间复杂度： O(1)

解法四

题目分析

由解法三可以想到，我们需要尽量多的剪掉不必要的行和列。而发现，如果从 左下角或者 右上角开始遍历，可以决定剪掉 当前行或者 当前列。从而只需要维持两个变量即可。

从左下角开始遍历，向上的方向是依次递减的，向右的方向是依次递增的。并且只能向上或者向右遍历；优先向右遍历，这样就可以剪掉小于`target`的列。遍历到对角点`右上角`时，表示未找到`target`；

从右上角开始遍历，向下的方向是依次递增的，向左的方向是依次递减的。并且只能向下或者向左遍历；优先向下遍历，这样就可以剪掉小于`target`的行。遍历到对角点`左下角`时，表示未找到`target`； 还以题目给出的示例为例：

[
  [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：

从左下角出发，走过的路径的为`18, 10, 3, 6, 5`

从右上角出发，走过的路径的为`15, 11, 7, 4, 5` 查找`target=20`：

从左下角出发，走过的路径的为`18, 10, 13, 17, 16, 12, 19, 15`，此时`6`和`14`都比`20`小，故不存在`20`；

从右上角出发，走过的路径的可能为`15, 19, 12, 16, 17, 14, 13, 10, 18`，未找到；

题目解答

左下角开始遍历：

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        int m = matrix.length;
        int n = matrix[0].length;

        int i = m - 1;
        int j = 0;
        while(i = 0 && j = n - 1) {
            if(matrix[i][j] == target) {
                return true;
            }
            // 若向右还有元素，并且小于target，则优先向右移动，否则向上移动
            if(j  n - 1 && matrix[i][j + 1] = target) {
                j ++ ;
            } else {
                i --;
            }
        }
        return false;
    }
}

复杂度分析：
时间复杂度： O(m + n)， 这里我们最多只需要迭代长度分别为 m、 n的数组。
空间复杂度： O(1)

右上角开始遍历：

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        int m = matrix.length;
        int n = matrix[0].length;

        int i = 0;
        int j = n - 1;
        while(i = m - 1 && j = 0) {
            if(matrix[i][j] == target) {
                return true;
            }
            // 若向下还有元素，并且小于target，则优先向下移动，否则向左移动
            if(i  m - 1 && matrix[i + 1][j] = target) {
                i ++ ;
            } else {
                j --;
            }
        }
        return false;
    }
}

复杂度分析：
时间复杂度： O(m + n)， 这里我们最多只需要迭代长度分别为 m、 n的数组。
空间复杂度： O(1)

参考资料

74. 搜索二维矩阵: https://leetcode-cn.com/problems/search-a-2d-matrix

75. 搜索二维矩阵 II: https://leetcode-cn.com/problems/search-a-2d-matrix-ii

原文始发于微信公众号（xiaogan的技术博客）：