面试题4：二维数组中的查找

题目一：

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

解法1： 依次遍历，但不是最优的结果，时间复杂度O(n*n),要点获取数组的行数列数，使用len(),对于二维数组返回的是行数，然后再对第一行元素len即可得到列数

 row, line = len(array),len(array[0])

解法2：动态规划的思想，不断地减小查找的范围，直到找到对应的数值或者遍历结束。根据该数组的特点，从右上角的元素或者左下角开始都可以。本代码从右上角开始与目标比较，如果相等，则返回true；如果该元素大于目标值，则说明元素所在列都大于目标值，于是查找范围中将该元素所在列排除；如果该元素小于目标值，该元素作为此行最大值，则说明本行不存在符合要求的元素，将该行排除。

该算法只需要O(n)的时间复杂度，比解法1更优。

# -*- coding:utf-8 -*-
class Solution:
    # array 二维列表
    def Find(self, target, array):
        # write code here
        row,line = len(array),len(array[0]) #二维数组len默认返回行数，对第一行元素求len即可得到列数
        if row==0 or line ==0:
            return False
        i = 0
        j = line-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