问答题 1.  在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请实现一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
    例如下面的二维数组就是符合这种约束条件的。如果在这个数组中查找数字7,由于数组中含有该数字,则返回true;如果在这个数组中查找数字5,由于数组中不含有该数字,则返回false。
    1    2    8    9
    2    4    9    12
    4    7    10    13
    6    8    11    15
【正确答案】最简单的方法就是对二维数组进行顺序遍历,然后判断待查找元素是否在数组中,这种方法的时间复杂度为O(M*N),其中,M,N分别为二维数组的行数和列数。
   虽然上述方法能够解决问题,但这种方法显然没有用到二维数组中数组元素有序的特点,因此,该方法肯定不是最好的方法。
   此时需要转换一种思路进行思考,一般情况下,当数组中元素有序的时候,二分查找是一个很好的方法,对于本题而言,同样适用二分查找,实现思路如下:
   给定数组array (行数:rows,列数:columns,待查找元素:data),首先,遍历数组右上角的元素(i=0,j=columns-1),如果array[i][j]==data,则在二维数组中找到了data,直接返回;如果array[i][j]>data,则说明这一列其他的数字也一定大于data,因此,没有必要在这一列继续查找了,通过j-操作排除这一列。同理,如果array[i][j]<data,则说明这一行中其他数字也一定比data小,因此,没有必要再遍历这一行了,可以通过i+操作排除这一行。依次类推,直到遍历完数组结束。
   实现代码如下:
   def findWithBinary(array,data):
   if array==None:
   return False
   #从二维数组右上角元素开始遍历
   i=0
   rows=len(array)
   columns=len(array[0])
   j=columns-1
   while i<rows and j>=0:
   #在数组中找到data, 返回
   if array[i][j]==data:
   return True
   #当前遍历到数组中的值大于data, data肯定不在这一列中
   elif array[i][j]>data:
   j-=1
   #当前遍历到数组中的值小于data, data肯定不在这一行中
   else:
   i+=1
   return False
   
   if __name__=="__main__":
   array=[[0,1,2,3,4],
   [10,11,12,13,14],
   [20,21,22,23,24],
   [30,31,32,33,34],
   [40,41,42,43,44]]
   print findWithBinaiy(array,17)
   print findWithBinary(array, 14)
   程序的运行结果为:
   false
   true
   算法性能分析:
   这种方法主要从二维数组的右上角遍历到左下角,因此,算法的时间复杂度为O(M+N),此外,这种方法没有申请额外的存储空间。
【答案解析】

[考点] 如何在有规律的二维数组中进行高效的数据查找。