15. 二维数组中的查找

问题描述

在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。

请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

样例

输入数组：

[
  [1,2,8,9]，
  [2,4,9,12]，
  [4,7,10,13]，
  [6,8,11,15]
]

如果输入查找数值为7，则返回true，

如果输入查找数值为5，则返回false。

解决方案

利用数组的特点，从第一行开始，我们每次让数组的每行的最后一个和目标值进行比较。具体算法如下：

1. 行序列 i 初始化为0，列序列 j 初始化为数组的列数；
2. 写一个while循环判断： array[i][j] 和 target 的大小关系：

• array[i][j] < target， 说明这一行的数都比较目标值小，则意味着行序列需要增加；
• array[i][j] > target， 说明目标值可能就在这行，我们让列序列减小；
• array[i][j] = target， 那就说明找到了，返回True就好了

3. 如果while循环都走完了，则只能说明这个数组中没有这个数，返回False

class Solution(object):
    def searchArray(self, array, target):
        """
        :type array: List[List[int]]
        :type target: int
        :rtype: bool
        """
        
        len_line = len(array) - 1
        if len_line <1:
            return False
        len_column = len(array[0])-1
        i = 0
        j = len_column
        while i <= len_line and j >= 0:
            if array[i][j] < target:
                i += 1
            elif array[i][j] > target:
                j -= 1
            else:
                return True
        return False