Search a 2D Matrix详解编程语言

Problem

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.

Example

Consider the following matrix:

[ 
    [1, 3, 5, 7], 
    [10, 11, 16, 20], 
    [23, 30, 34, 50] 
]

Given target = 3, return true.

Challenge

O(log(n) + log(m)) time

题解：一次二分搜索 VS 两次二分搜索

一次二分搜索 – 由于矩阵按升序排列，因此可将二维矩阵转换为一维问题。对原始的二分搜索进行适当改变即可(求行和列)。时间复杂度为 O(log(mn))=O(log(m)+log(n))
两次二分搜索 – 先按行再按列进行搜索，即两次二分搜索。时间复杂度相同。

显然我们应该选择一次二分搜索，直接上 lower bound 二分模板。

Java：

public class Solution { 
    /** 
     * @param matrix, a list of lists of integers 
     * @param target, an integer 
     * @return a boolean, indicate whether matrix contains target 
     */ 
    public boolean searchMatrix(int[][] matrix, int target) { 
        if (matrix == null || matrix.length == 0 || matrix[0] == null) { 
            return false; 
        } 
 
        int ROW = matrix.length, COL = matrix[0].length; 
        int lb = -1, ub = ROW * COL; 
        while (lb + 1 < ub) { 
            int mid = lb + (ub - lb) / 2; 
            if (matrix[mid / COL][mid % COL] < target) { 
                lb = mid; 
            } else { 
                if (matrix[mid / COL][mid % COL] == target) { 
                    return true; 
                } 
                ub = mid; 
            } 
        } 
 
        return false; 
    } 
}

源码分析

仍然可以使用经典的二分搜索模板(lower bound)，注意下标的赋值即可。

首先对输入做异常处理，不仅要考虑到matrix为null，还要考虑到matrix[0]的长度也为0。
由于 lb 的变化处一定小于 target, 故在 else 中判断。

复杂度分析

二分搜索，O(logn).

原创文章，作者：奋斗，如若转载，请注明出处：https://blog.ytso.com/20716.html