Search a 2D 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:

    Challenge

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

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

    Python

    Java

    lower bound 二分模板。

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

    复杂度分析

    二分搜索，O(\log mn).

    源码分析

    1. 再在这一行中找target

    复杂度分析

    二分搜索， O(\log m + \log n)