【Python刷面试题】：杨氏矩阵搜索算法

题目

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

解析

Step-wise线性搜索解法

从右上角开始，每次将搜索值与右上角的值比较，如果大于右上角的值，则直接去除1行，否则，则去掉1列。如下图显示了查找13的轨迹。首先与右上角15比较，13<15，所以去掉最右1列，然后与11比较，这是13>11，去掉最上面1行…以此类推，最后找到13。算法复杂度O(n)，最坏情况需要m+n步，即从右上角开始查找，而要查找的目标值在左下角的时候。

代码

"""
1.杨氏矩阵查找
"""
def find(l,a):
    m = len(l)
    n = len(l[0])

    i = 0
    j = n - 1
    while i < m and j >= 0:
        temp = l[i][j]
        if a == temp:
            return True
        elif a > temp:
            i += 1
        else:
            j -= 1
    return False

l = [[1,2,3],[4,5,6],[7,8,9]]

print(find(l,-1))
print(find(l,5))
print(find(l,10))

False
True
False

参考：
1.https://blog.csdn.net/sgbfblog/article/details/7745450
2.https://github.com/taizilongxu/interview_python#4-%E6%9D%A8%E6%B0%8F%E7%9F%A9%E9%98%B5%E6%9F%A5%E6%89%BE