剑指Offer 1 ：二维数组的查找

题目：

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

题目给出的是一个递增的二维数组
实现一个二维数组

1   2    8    9
2   4    9    12
4   7    10   13
6   8    11   15

list = [[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]
遍历所有的数，找到这个数

def Find(target, array):
        i_max = len(array)
        j_max = len(array[0])-1
        i,j = 0,j_max
        while i < i_max and j >= 0:
            if target == array[i][j]:
                return 1
            elif array[i][j] > target:
                j = j - 1 
            else:
                i = i + 1
        return 0

上面这个纯粹闹着玩，下面写算法思想：
从左上角开始找这个数，因为二维数组是有序的，如果查找的数字大于数组中现在这个数字，那么这个数字应该是这个数字的下方或者右方，会出现重叠的部分，再想办法处理这个重叠的部分，得不偿失，换角
从右上角找：如果数组中的数大于key则不可能在这个数所在的列，删除这一列
如果数组中的数小于key则不能在这一行（因为我们每次取得都是右上角的数，所以这个数的右边没有数，所以这一行都可以删掉。）同理还可以从左下角开始找
代码（右上角）

def findKey(a,key):
    i,j =0,3# i 行
    while i <= 3 and j >= 0:
        print i,j
        print list[i][j]
        if key == list[i][j]:
            print "true"
            return
        elif list[i][j] > key:
            j = j - 1 
        else:
            i = i + 1
    print "false"

ps:上面这个直接传入了数组的长宽，如果改为更通用的可以用len(a)和len(a[0])