二维数组的查找

在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

注意这里可能会引入歧途。比如我开始的思路是，先二分查找target在哪一行（原则上本行开始数据小于target，下行开始数据大于target，就是要找的），然后找到行就简单的二分查找在哪一列就行。结果这是个完全错误的思路。。。
举例：数组为
1 2 3
2 5 6
3 8 9
tareget = 5
按照上面的思路会到第三行找。。。。

如果本题真的要二分找，只能对每一行，或者每一列去进行
复杂度为nlog(m)

一种最佳的思路是，根据数组的特点，从数组的右上角(或者左下角)始找。如果tareget大于右上角的数据，说明这一行都不行，因为右上角是这一行最大的数据了。反之如果小于右上角数据，说明这一列都不行，因为右上角是这一列最小的数据了。这样复杂度为O(m+n)

class Solution:
    # array 二维列表
    def Find(self, target, array):
        # write code here
        
        # first find row
        if not array or not target:
            return False
        row = len(array)
        if row < 1:
            return False
        col = len(array[0])
        if col<1 :
            return False
        
        if target<array[0][0] or target>array[-1][-1]:
            return False

        i = 0
        j = col-1
        while i<row and j>=0:
            if array[i][j] == target:
                return True
            elif array[i][j] > target:
                j -= 1
            else:
                i += 1
        return False