二维数组的查找

题目描述

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

解题思路

+ 由于这个二维数组的每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。那么可以知道每一行的最后一个数是最大的，每一列中下面的数比上面的大。 + 所以我们先从右上角的那个元素找起，如果刚好等于target那么就找到了，如果target > array[i][j]，那么说明第i行一定没有这个数，只能往下一行去找，即 i += 1。反之， 如果target < array[i][j]，说明target就在当时 i 这行，具体哪一列就往前去找，即j -= 1

# -*- coding:utf-8 -*- class Solution: # array 二维列表 def Find(self, target, array): # write code here rows = len(array)-1 i = 0 j = len(array[0])-1 while i <= rows and j >= 0: if target == array[i][j]: return True elif target > array[i][j]: i += 1 else: j -= 1 return False