The O(m+n) loop code is everywhere in the discussion, here I post my O(log(4/3, M) + log(4/3, N)) code, but it is much slower in time. I guess it is because of the recursion. Any idea?

class Solution(object):

```
def searchMatrix(self, matrix, target):
if len(matrix) == 0 or len(matrix[0]) == 0:
return False
rowL = 0
rowH = len(matrix) - 1
colL = 0
colH = len(matrix[0]) - 1
return self.binarySearch(matrix, rowL, rowH, colL, colH, target)
def binarySearch(self, matrix, rowStart, rowEnd, colStart, colEnd, target):
if rowStart > rowEnd or colStart > colEnd:
return False
if rowStart == rowEnd and colStart == colEnd:
if matrix[rowStart][colStart] == target:
return True
else:
return False
rowM = (rowStart + rowEnd) / 2
colM = (colStart + colEnd) / 2
if matrix[rowM][colM] < target:
#search all blocks except upper left block
return self.binarySearch(matrix, rowM+1, rowEnd, colStart, colEnd, target) \
or self.binarySearch(matrix, rowStart, rowM, colM+1, colEnd, target)
elif matrix[rowM][colM] > target:
#search all blocks except right bottom block: upper right, upper left
return self.binarySearch(matrix, rowStart, rowM-1, colM+1, colEnd, target) \
or self.binarySearch(matrix, rowStart, rowM, colStart, colM, target) \
or self.binarySearch(matrix, rowM+1, rowEnd, colStart, colM-1, target)
else:
return True
```