题目：在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
例如：下面的二维数组，每行每列都是递增排序，如果在这个数组中查找target数字7，则返回true；如果查找数字5，则返回false
1 2 8 9
2 4 9 12
4 7 10 13
6 8 11 15
思考1：易入误区
在看到这个题时，第一反应这是一个有序数组，是不是可以用有序列表的思路来进行思考呢，用上二分查找之类的方法。但是细想一下，就会发现，如果从左上角开始查找，如果命中还好说，不命中就需要向右或者向下查找，这样每一次判断结果小了都会有向右或者向下两种情况，就没法查了。
思考2：正确思路
这个题的关键是从右上角开始查，如果命中target则返回true。如果右上角的值大于target的值，根据数组的递增的特性，右上角所在列的所有元素都会比target的值要大，因此就可以删除右上角所在列。如果右上角的值小于target的值，根据数组递增的特性，其值所在一行的元素的值都会比target小，因此可以删掉该行。然后依次判断出于右上角的值即可确定结果。
总结如下：
从右上角（左下角）开始找，
1)命中，查找成功
2)右上角数字比target大，删除最右一行
3）右上角比target小，删除上一行
PS：类似的，从左下角开始查找也是相同的道理。
PS2：该算法的利用的是夹逼的思想，不断从左右进行逼近，直至最终结果。
Python代码如下：
class Solution:
# array 二维列表
def Find(self, target, array):
m = len(array) - 1
n = len(array[0]) - 1
i = 0
while i <= m and n >= 0:
if array[i][n] == target:
return True
elif array[i][n] > target:
n -= 1
elif array[i][n] < target:
i += 1
return False
def searchNum(self,target, array):
'''
搜索递增列表中包含几个target
'''
m = len(array) - 1
n = len(array[0]) - 1
i = 0
count = 0
while i <= m and n >= 0:
if array[i][n] == target:
count += 1
i += 1
elif array[i][n] > target:
n -= 1
elif array[i][n] < target:
i += 1
return count
arr = [[1,4,8,9],
[4,7,10,13]]
target = 4
s = Solution()
print s.Find(target,arr)
print s.searchNum(target,arr)
以上算法中find方法即为查找方法，searchNum是拓展部分的内容，用来检查数组中有几个target值。
PS3：上面的算法可以通过牛客网上的剑指offer在线OJ
https://www.nowcoder.com/practice/abc3fe2ce8e146608e868a70efebf62e?tpId=13&tqId=11154&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
