剑指Offer-001：二维数组中的查找

一、前言

本系列文章为《剑指Offer》刷题笔记。

刷题平台：牛客网

二、题目

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

1、思路

首先选取数组中右上角的数字。如果该数字等于要查找的数字，查找过程结束；如果该数字大于要查找的数组，剔除这个数字所在的列；如果该数字小于要查找的数字，剔除这个数字所在的行。也就是说如果要查找的数字不在数组的右上角，则每一次都在数组的查找范围中剔除一行或者一列，这样每一步都可以缩小查找的范围，直到找到要查找的数字，或者查找范围为空。

2、举例

如果在一个二维数组中找到数字7，则返回True，如果没有找到，则返回False。

 查找过程如下：

 3、编程实现

#! /usr/bin/env python3
# -*- coding:utf-8 -*-

# Author   : Ma Yi
# Blog     : http://www.cnblogs.com/mayi0312/
# Date     : 2020-04-22
# Name     : test01
# Software : PyCharm
# Note     : 在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增排序。请完成一个
#            函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。


class Solution:
    # array 二维列表
    @staticmethod
    def find_num(target, array):
        # write code here
        i_rows = len(array)  # 行
        i_cols = len(array[0])  # 列
        if i_rows == 0 or i_cols == 0:
            return False
        i_row = 0
        i_col = i_cols - 1
        while i_row < i_rows and i_col >= 0:
            if target == array[i_row][i_col]:
                return True
            elif target < array[i_row][i_col]:
                i_col -= 1
            else:
                i_row += 1

        return False


def main():
    l_array = [[1, 2, 8, 9], [2, 4, 9, 12], [4, 7, 10, 13], [6, 8, 11, 15]]
    result = Solution.find_num(7, l_array)
    print(result)

if __name__ == '__main__':
    main()