剑指 Offer 04. 二维数组中的查找

描述：在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

tags: binary search

思路

利用数组有序的定义，使用二分查找法。从左下或右上出发，例从左下出发，找到返回，大于target则向上，小于则向右

class Solution:
    def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool:
        m = len(matrix)
        if m == 0:
            return False
        n = len(matrix[0])
        x = 0
        y = n - 1
        while x < m and y >= 0:
                cur = matrix[x][y]
                if cur == target:
                    return True
                elif cur < target:
                    x += 1
                elif cur > target:
                    y -= 1
        return False