剑指offer(1)：二维数组中的查

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

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

2017080715020726668160.png

思路：从右上角开始查找, 如果该数字等于要查找的数字，查找结束
                    如果该数字大于要查找的数字，说明当前列不可能存在这个数;
                    如果小于要查找的数字, 说明当前行不可能存在这个数.

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# Created by xuehz on 2017/7/15

class Solution:

    def Find(self, array, target):
        row = len(array)
        column = len(array[0])

        if row > 0 and column > 0:
            x ,y = 0, column -1 #0,3 找到右上角的数字

            while 0 <= x <row and 0 <= y < column:
                if array[x][y] == target:
                    return True
                elif array[x][y] > target: # 说明当前列不会有这个数了
                    y -= 1
                elif array[x][y] < target: # 说明当前行不会有这个数了
                    x += 1
        return False


    def Find1(self, array, target):
        flag = False
        # 借助于in
        for index in range(len(array)):
            if target in array[index]:
                flag = True
        return flag

if __name__ == '__main__':

    array_ = [[1, 2, 8, 9],
         [2, 4, 9, 12],
         [4, 7, 10, 13],
         [6, 8, 11, 15],
         ]
    s = Solution()
    print s.Find1(array_, 7)