剑指offer—面试题4： 二维数组中的查找

在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
如下面的二维数组，给定 target = 5，返回 true。给定 target = 20，返回 false。

[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]

首先要分析查找的顺序，给定一个数字如果改数字不匹配，应该如何转到下一个数字进行比对。下图给出了分析的过程。

4361607779912_.pic_hd.jpg

程序可以从右上角或者左下角开始比较。但不能从右下角或者是左上角开始，因为右上角或者左下角每次比较我们都可以排除一列或者是一行。如果右下角或者是左上角开始。假设是右上角开始，1 < 5。 但 1 同时是第一行、第一列的最小值我们无法排除第一行、第一列其它数据是否会大于5.

以例子中的二维数组为例，假设要查找的target为5时，我们从右上角开始，5 < 15,15是第5列最小的数字所以第5列排除，下次比较第四列开始，一次比较到第二列「4」时。5 > 4 ，下一个从第二行比较 5=5 。找到 target。

代码（取右上角开始）：

 func findNumberIn2DArray(_ matrix: [[Int]], _ target: Int) -> Bool {

        if matrix.count == 0 {
            return false
        }
        var row = 0
        var column = matrix.first!.count - 1
        
        while row < matrix.count && column >= 0{
            
            if(matrix[row][column] > target){
                column -= 1
            }else if(matrix[row][column] < target) {
                row += 1
            }else {
                return true
            }
        }
        return false
    }