【LintCode 简单 】28. 搜索二维矩阵

1.问题描述：

写出一个高效的算法来搜索 m × n矩阵中的值。

这个矩阵具有以下特性：

• 每行中的整数从左到右是排序的。
• 每行的第一个数大于上一行的最后一个整数。

2.样例：

样例  1:
    输入: [[5]],2
    输出: false
    
    样例解释: 
  没有包含，返回false。

样例 2:
    输入:  
[
  [1, 3, 5, 7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
],3
    输出: true
    
    样例解释: 
    包含则返回true。

3.代码：

class Solution:
    """
    @param matrix: matrix, a list of lists of integers
    @param target: An integer
    @return: a boolean, indicate whether matrix contains target
    """

    def searchMatrix(self, matrix, target):
        # write your code here
        m = len(matrix)
        n = len(matrix[0])
        mm = 0
        if target < matrix[0][0]:
            return False
        for i in range(m):
            print(i)
            if target >= matrix[i][0] and target <= matrix[i][n - 1]:
                mm = i
                break
        for j in range(n):
            if target == matrix[mm][j]:
                return True
        return False

注意：这里所给的matrix实际是一个二维的list，没有shape属性，需要通过len()方法来获取它的m和n。另外，这里时间复杂度是O(m)+O(n)，如果想要实现O(log(m)+log(n))的话，需要使用二分搜索方法。