Search a 2D Matrix

Question

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

Integers in each row are sorted from left to right. The first integer of each row is greater than the last integer of the previous row. For example,

Consider the following matrix:

[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]

Given target = 3, return true.

Thought

Many solutions take the 2d matrix as the 1d sorted list and use the index = col * row to get the items in the 2d matrix. However, this is not a good idea:

1. The time complexity is not improved at all. The time complexity for both of them are O(log(m) + log(n)) or we can say O(log(m*n)), which are equal in maths.
2. col * row may cause overflow when the matrix is insanely huge.
3. The multiplication and mod are expensive in fact.

Thus, I determined to use the binary search two times here for the 2d matrix. First time is used to find the corresponding row and the second time is used to find the specific spot in that row.

Code

class Solution(object):
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        # use the first element in each row to determine sublist quickly and search the sublist
        if matrix == [] or matrix == [[]]:
            return False
        # get the height and width
        height, width = len(matrix), len(matrix[0])
        if matrix[0][0] > target or matrix[-1][-1] < target:
            return False
        begin, end = 0, height - 1
        while begin < end - 1:
            mid = (begin + end) / 2
            if matrix[mid][0] == target:
                return True
            elif matrix[mid][0] < target:
                begin = mid
            else:
                end = mid
        if matrix[end][0] <= target:
            idx = end
        else:
            idx = begin
        begin, end = 0, width - 1
        while begin < end - 1:
            mid = (begin + end) / 2
            if matrix[idx][mid] == target:
                return True
            elif matrix[idx][mid] < target:
                begin = mid
            else:
                end = mid
        if matrix[idx][begin] == target or matrix[idx][end] == target:
            return True
        else:
            return False