剑指offer面试题03----二维数组中的查找

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

例如：下面的二维数组，每行每列都是递增排序，如果在这个数组中查找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