剑指Offer系列算法题-有序二维数组查找

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

实现思路: 由于这个二维数组是每行有序，每列有序。所以可以这样

1. 可以每次选取二维数组中，右上角的数字。
2. 若该数字等于该查找的数字，则查找过程结束。
3. 如果该数字小于要查找的数字，则可以排除此行的其他数字
4. 如果该数字大于要查找的数字，则可以排行此列及后面的每一列
5. 重复第一步，直到把所有的行和列都排除掉

代码实现: Swift
这里的实现是对Swift里的Array添加了contains函数，这个contains函数利用泛型限制Array里的元素的类型必须是Array，并且子Array里的元素必须是遵循Comparable协议

extension Array{
    func contains<C:Comparable>(element:C) -> Bool where Element == Array<C>  {
        let count = self.count
        var line = 0
        var maxRow:Int?
        while line < count && (maxRow == nil || maxRow! >= 0){
            let row = maxRow != nil ? Swift.min(maxRow!, self[line].count - 1) : (self[line].count - 1)
            let currentElement = self[line][row]
            if currentElement == element {
                return true
            }else if currentElement < element {
                line += 1
            }else {
                if maxRow != nil {
                    maxRow! -= 1
                }else {
                    maxRow = row - 1
                }
            }
        }
        return false
    }
}
<!--测试-->
let array = [[1,2,8,9,10],[2,4,9,12],[4,7,10,10,13],[6,8,11,15,18,20]]
for number in 0..<22 {
    print("数组中\(array.contains(element: number) ? "包含" : "不包含")\(number)")
}

测试结果
针对 [[1,2,8,9,10],[2,4,9,12],[4,7,10,10,13],[6,8,11,15,18,20]]这个数组，测试了从最小值-1到最大值+1（0-21）之间的所有数据，显示结果是正确的