# Python iterative and recursive solutions.

• ``````# O(m*n) space, O(lg(m*n)) time
def searchMatrix1(self, matrix, target):
if not matrix or target is None:
return False
ls = reduce(lambda x, y: x + y, [row for row in matrix], [])
l, r = 0, len(ls)-1
while l <= r:
mid = l + (r-l)//2
if ls[mid] < target:
l = mid + 1
elif ls[mid] > target:
r = mid - 1
else:
return True
return False

# Iteratively
def searchMatrix(self, matrix, target):
if not matrix or target is None:
return False
l, r = 0, len(matrix) * len(matrix[0]) - 1
while l <= r:
mid = l + (r-l)//2
row, col = mid//len(matrix[0]), mid%(len(matrix[0]))
if matrix[row][col] < target:
l = mid + 1
elif matrix[row][col] > target:
r = mid - 1
else:
return True
return False

# Recursively
def searchMatrix3(self, matrix, target):
if not matrix or target is None:
return False
return self.helper(matrix, 0, 0, len(matrix)-1, len(matrix[0])-1, target)

def helper(self, matrix, x1, y1, x2, y2, target):
while x1 <= x2 and y1 <= y2:
midx = x1 + (x2-x1)//2; midy = y1 + (y2-y1)//2
if target < matrix[midx][midy]:
return self.helper(matrix, x1, y1, midx-1, y2, target) or \
self.helper(matrix, midx, y1, midx, midy-1, target)
elif target > matrix[midx][midy]:
return self.helper(matrix, midx+1, y1, x2, y2, target) or \
self.helper(matrix, midx, midy+1, midx, y2, target)
else:
return True
return False``````

• "O(lg(m*n)) time"

It's nowhere near O(lg(mn)). It's not even O(mn). It's Θ(m2n), as the line

``````ls = reduce(lambda x, y: x + y, [row for row in matrix], [])
``````

is really costly. And btw also a really complicated way to write

``ls = sum(matrix, [])``

• I am not sure whether the complexity of the reduce clause is O(mmn) while ls = sum(matrix, []) is much shorter.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.