剑指offer：二维数组中的查找

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

创新互联网站建设公司提供网站设计和自适应建站服务。团队由有经验的网页设计师、程序员和市场专家组成，能够提供从H5技术，网站制作，广告投放平台，模板建站到微信平台小程序开发等全方位服务。 以客户为中心，致力于为客户提供创新、高效的解决方案，帮助您打造成功的企业网站。

题目分析：
由于所给的二维数组在一定程度上是有序的，即每一行、每一列都是有序的，但是行与行之间不一定是有序的。如：

1 2 3
2 3 4
3 4 5

第二行的2和第一行的3并不是有序的。
因此，如果从左上角坐标为(0, 0)开始遍历这个二维数组的话，如果当前的数字小于要查找的目标数字，那么要查找的数字就可能出现在当前数字的右边或左边，导致问题变复杂。
相反，如果我们换个思路，从数组的左下角或者右上角开始遍历，以左下角为例，如果当前的数字小于目标数字，那么就往右查找，反之往上查找。这样每次判断完之后只有一个方向需要遍历，问题就变得不复杂了。

# -*- coding:utf-8 -*-
class Solution:
    # array 二维列表
    def Find(self, target, array):
        m, n = len(array), len(array[0])
        i, j = m - 1, 0  # 从左下角开始
        while i >= 0 and j < n:  # 因为我们只会往右、往上走，所以i只会减，j只会加，因此只需要保证i,j不越界即可
            if array[i][j] == target:
                return True
            if array[i][j] > target:  # 目标数字比当前数字小，往上
                i -= 1
            else:  # 目标数字比当前数字大，往右
                j += 1

        return False