题目描述
在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
解法思路
逐个遍历
这种题目思路不难，最直接的想法只需要挨个遍历即可。这个方法的问题在于，时间复杂度比较高。
优化查找
为了加快搜索速度，就需要用到题目中给的额外信息：“每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序” 。
我们会尝试着画出这个数组的矩阵形式，以下图为例：
当我们对目标数进行查找的时候会有三种情况：
- 当前数比目标数大，则目标数在当前数的左上角
- 当前数比目标数小，则目标数在当前数的右下角
- 当前数等于目标数，搜索结束
所以我们对遍历的起点做了一点改变，我们不再是逐行再逐列搜索，而是从左下角（或者右上角）作为起点。
比如，设要搜索的整数为m，数组A的大小为n*n，我们从左下角开始，m先和左下角的A[n-1][0]做比较，如果m>A[n-1][0], 则m已经大于第一列的任何数，只需要右移一位，再和A[n-1][1]比较；如果m<A[n-1][0], 则m已经小于最后一行的任何数，只需要上移一位，再和A[n-2][0]比较。依次迭代，即可找到该整数，当没法上移或者右移且没有找到该数，则说明这个数不在二维数组中。
从右上角查找的过程也是类似的。
以上面的矩阵A为例，设要查找的数为2.5，则查找过程如上图，最后无法继续移动，则查找结束，该数不存在。
复杂度分析
逐行挨个遍历的时间复杂度很简单，为 $O(n^2)$ 。
优化后的方法，比对的次数最多为2*n - 1，所以算法的复杂度为 $O(n)$。
从顺序查找的$O(n^2)$ 降低到$O(n)$，优化后时间复杂度为原来的的对数。可以联想到，长度为n的有序一维数组顺序查找，复杂度为$O(n)$，而使用二分法查找的时间复杂度为$O(log_2n)$，同样为原来的对数。
没错，因为二维数组内部存在了有序关系，所以实际上我们也是用到了二分法的思想。
具体二维数组的有序性可以参考下面的图：
图中的红色框和蓝色框，表示从二维数组中抽取出来的两个一维数组。（这里采用的是先取列再取行的抽取方法，先取行再取列也是一样的）
很显然，这些一维数组都是递增有序的。
对于二维矩阵A，假设我们以左上角作为起点，开始查找，则开始的位置处于递增一维有序数组的开头，而当我们从左下角开始查找，开始的位置处于一维有序数组的中间位置，比对一次后，便可以排除最多n个元素。然后相应地移动到另外一个一维有序数组中进行比对。
比如上图的矩阵，m先与左下角的4比对，对应的一维有序数组为红色框的数组，m小于4,则比对位置移动至上一行的3，对应的一维有序数组为蓝色框的数组。在这一步过程中，排除掉了最后一行的n个元素。
相比之下，逐点比对，每一次比对只能排除掉一个元素。因此大大降低列时间复杂度。
代码
# -*- coding:utf-8 -*-
class Solution:
# array 二维列表
def Find(self, target, array):
# write code here
# 从右上角开始查找
i = 0
j = len(array[0])-1
row = len(array) #获取矩阵的shape
flag = False
while i<row and j>=0:
if target>array[i][j]:
i+=1
elif target<array[i][j]:
j-=1
elif target == array[i][j]:
flag = True
break
return flag
