Using Python to search a sorted 2D Matrix Code

Problem

class Solution:
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """

        if len(matrix) == 0 or len(matrix[0]) == 0:
            return False

        height = len(matrix)
        width = len(matrix[0])

        row = height - 1 
        col = 0

        while col &lt; width and row &gt;= 0:
            if matrix[row][col] &gt; target:
                row -= 1
            elif matrix[row][col] &lt; target:
                col += 1
            else:
                return True

        return False


Any improvements you could make to this? Runtime is O(Len(row) + len(col)), space is constant.

I looked at other solutions and a lot of them used binary search, but that is O(len(col) * log(len(row)) so I don't think that's an improvement.
Unfortunately, using binary search both for rows and columns is not possible here. It fails if the last element of the first row is too small, i.e. for this input:

matrix = [[ 0,  1,  2,  3,  4,  5],
          [ 6,  7,  8,  9, 10, 11],
          [12, 13, 14, 15, 16, 17],
          [18, 19, 20, 21, 22, 23],
          [24, 25, 26, 27, 28, 29]]
target = 10


However, you could use binary search within each row for \$\mathcal{O}(n\log m)\$ runtime, compared to your \$\mathcal{O}(n + m)\$ runtime, as you noted in the question. While this is nominally worse, for the actual testcases being tested by Leetcode it performs better.

from bisect import bisect_left

class Solution:
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        if not matrix or not matrix[0]:
            return False
        for row in matrix:
            i = bisect_left(row, target)
            if i &lt; len(row) and row[i] == target:
                return True
        return False


Your code: 36ms, faster than 85.35%

Binary search: 28 ms, faster than 98.39%

This is probably due to the testcases being small enough (and  if \$m = n\$, \$2n &gt; n\log_b n\$ for \$n &lt; b^2\$).