Leetcode 74 - Search a 2D Matrix

Utilize binary search

Search a 2D Matrix 搜寻一个二维数组

题目:

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

Integers in each row are sorted from left to right.

The first integer of each row is greater than the last integer of the previous row.

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

题意很好理解,便是从一个二维数组中寻找一个值。如果存在这个值,便返回true,否则false。值得注意的是这个数组的行和列都是从小到大排序的,并且每一行的第一个值都比前一行的最后一个值大。这个性质之后可以用到。

Approach One: Brute Force 暴力解:

第一种解非常容易想到,便是对矩阵的每一列及每一行进行遍历,如果找到值,就返回true,否则返回false。

时间复杂度: O(n*m)。n和m为数组的行和列的长度。
空间复杂度: O(1)。 没有用到额外的空间。

可以看到时间复杂度非常大,可能会导致超时,所以我们想一个其他方法。

Approach Two: Variation of Linear Search 线性寻找(kind of)

第二种方法是从这个矩阵的一个角开始找起,以下的code是从矩阵的右上角开始,如果当前的值比要寻找的值小,则往前看一位(也就是往前看一列),反之则往下看一位(也就是往下看看一行)直到找到为止,找不到就返回false。这个方法用到了矩阵的行和列是排好序的性质。

时间复杂度: O(n+m)。n和m为数组的行和列的长度。最差的情况便是从一个角遍历到了对角(e.g. 从右上角遍历到了左下角)。
空间复杂度: O(1)。 没有用到额外的空间

    // linear search: O(n+m)
    public boolean searchMatrix(int[][] matrix, int target) {
        if(matrix==null||matrix.length==0) return false;
        int row=0, col=matrix[row].length-1;
        while(row<matrix.length && col>=0) {
            if(matrix[row][col]==target) {
                return true;
            } else if(matrix[row][col]>target) {
                col--;
            } else{
                row++;
            }
        }
        return false;
    }

Approach Three: 二分搜索法

由于行和列是排序的,所以很容易联想到二分搜索。即是先对对矩阵的行进行查找,当找到一个可能包含这个值的行时,再进行第二次二分搜索。注意的是必须先对行进行查找,也就是matrix[row][0],不然会有bug。

时间复杂度: O(logn+logm)。n和m为数组的行和列的长度。每次只需寻找当前数组范围的一半。
空间复杂度: O(1)。 没有用到额外的空间

    // Binary Search: O(logn+logm)
    public boolean binarySearchMatrix(int[][] matrix, int target) {
        if(matrix==null || matrix.length==0 || matrix[0].length==0) return false;
        int up=0, bot=matrix.length-1, mid=0;
        while(up<=bot) {
            mid=up+(bot-up)/2;
            if(matrix[mid][0]==target) {
                return true;
            } else if(matrix[mid][0] < target) {
                up=mid+1;
            } else {
                bot=mid-1;
            }
        }
        if(matrix[mid][0] > target){
            if(mid == 0){
                return false;
            }
            mid--;//mid-1
        }
        int row=mid;

        // Manually write the binary search
        /**
        int l=0, r=matrix[l].length-1, row=mid;
        while(l<=r) {
            mid=l+(r-l)/2;
            if(matrix[row][mid] == target) {
                return true;
            } else if(matrix[row][mid] < target) {
                l=mid+1;
            } else {
                r=mid-1;
            }
        }
        */

        // Used binary search api in java
        return Arrays.binarySearch(matrix[row], target)>=0;
}