来源：剑指offer 面试题 4

题目：二维数组中的查找

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

例如下面的二维数组就是每行、每列都递增排序。如果在这个数组中查找数字 7，则返回 true；如果查找数字 5，由于数组不含有该数字，则返回 false。

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

解决思路

  • 用具体的问题入手

本题以 7 为查找对象，其步骤如下：

先取右上角的数字 9，由于 9 大于要查找的 7 ，故 7 肯定不在此列，删除此列，如 (a) 所示；再取新的数字 8 ，同理 8 大于 7，不在此列，删去，此时只剩下两列，如 (b) 所示。
在剩余的两列中，右上角的 2 比 7 小，故 7 应该在 2 的下方，删除此行，如 (c) 所示；再取新的右上角的数 4，同理，7 只可能在 4 的下方，故删除此行。如 (d) 所示；
在剩余的两行两列中，再取右上角的数 7 ，此时和查找的数相同，结束，如不相同，则继续。

可以选取右上角或者左下角作为初始值，但是不能选择左上角和右下角，因为我们没办法是拿出某一行或者某一列，这样就不能缩小范围

剑指Offer04：二维数组中的查找 - 图1

代码实现

测试用例：

  • 要查找的数在数组中
  • 要查找的数字不在数组中（大于数组中所有的值，小于数组中所有的值，在某两个数字之间）
  • 空数组
  1. # -*- coding:utf-8 -*-
  2. class Solution:
  3.     # array 二维列表
  4.     # target 要查找的数
  5.     def Find(self, target, array):
  6.         found = False  # 标志位
  7.         rows = len(array) 
  8.         cols = len(array[0])
  9.         if ((rows > 0) and (cols > 0)): # 边界检测
  10.             row = 0
  11.             col = cols - 1  # 从最后一列开始检查
  12.             while((row < rows) and (col >= 0)):
  13.                 if array[row][col] == target: # 右上角的值与目标值相等就返回
  14.                     found = True
  15.                     break
  16.                 elif array[row][col] > target: # 右上角的值比目标值大，去掉最后一列
  17.                     col -= 1
  18.                 else: # 当右上角的值比目标值小，就去掉这一行
  19.                     row += 1 
  20.         return found
  24. def test1(f): # 查找的数在数组中
  25.   target = 7
  26.   arr = [[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]
  27.   assert f.Find(target, arr) == True
  30. def test2(f):  # 空数组
  31.   target = 7
  32.   arr = [[]]
  33.   assert f.Find(target, arr) == False
  36. def test3(f):  # 查找的数不在数组中
  37.   target = 5
  38.   arr = [[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]
  39.   assert f.Find(target, arr) == False
  42. def Test():
  43.   f = Solution()
  44.   test1(f)
  45.   test2(f)
  46.   test3(f)
  49. Test()
class Solution:
    def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool:    
        rows = len(matrix)
        cols = 0
        if rows > 0:
            cols = len(matrix[0])
        if rows == 0 or cols == 0:
            return False
        row = 0
        col = cols-1
        while row < rows and col >= 0:
            if matrix[row][col] == target:
                return True
            if matrix[row][col] > target:
                col -= 1
            if matrix[row][col] < target:
                row += 1
        return False

参考