3.5 Search a 2D Matrix搜索二维矩阵

在线题测：http://www.lintcode.com/en/problem/search-a-2d-matrix/

在线题解： https://www.jiuzhang.com/solution/search-a-2d-matrix/#tag-highlight-lang-python

28.搜索二维矩阵

中文

English

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

这个矩阵具有以下特性：

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

样例

样例  1:
    输入: [[5]],2
    输出: false

    样例解释: 
  没有包含，返回false。

样例 2:
    输入:  
[
  [1, 3, 5, 7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
],3
    输出: true

    样例解释: 
    包含则返回true。

挑战

O(log(n) + log(m)) 时间复杂度

更新代码：

PS： python 2 运行结果

class Solution:
    """
    @param matrix, a list of lists of integers
    @param target, an integer
    @return a boolean, indicate whether matrix contains target
    """
    def searchMatrix(self, matrix, target):
        if len(matrix) == 0:
            return False

        n, m = len(matrix), len(matrix[0])
        start, end = 0, n * m - 1
        while start + 1 < end:
            mid = (start + end) / 2
            x, y = mid / m, mid % m
            if matrix[x][y] < target:
                start = mid
            else:
                end = mid
        x, y = start / m, start % m
        if matrix[x][y] == target:
            return True

        x, y = end / m, end % m
        if matrix[x][y] == target:
            return True

        return False