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

题目描述

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

解题思路

时间复杂度 O(n)的解题方法：

1.首先判断二维数组是否为空，不要遗忘掉

2.从二维数组的右上角array[0][len(array[0])-1]开始做比较，向左递减，向下递增；如果该数字大于target，则删除该数字所在列，如果该数字小于target，则删除该数字所在行。

# -*- coding:utf-8 -*-
class Solution:
    def Find(self, target, array):
        # write code here
        if len(array) == 0:
            return False
        row = 0
        col = len(array[0]) - 1
        #从右上角array[0][len(array[0])-1]开始做比较，向左递减，向下递增
        while row < len(array) and col >= 0:
            if array[row][col] == target:
                return True
            elif array[row][col] > target:
                col = col - 1
            else:
                row = row + 1
        return False