# Search in sorted matrix NxM

The problem (from Cracking the Coding book):

Given an NxM matrix in which each row and each column is sorted in ascending order, write a method to find an element.

I thought of a modified version of binary search, and I haven't found this solution anywhere on the internet (some solution about quad partitioning is very similar as seen in this link).

Here's my solution:

def search(elem, matrix, up, down, left, right):

if up > down or right < left:
return None

mid_row = int((up + down) / 2)
mid_col = int((left + right) / 2)

mid_elem = matrix[mid_row][mid_col]

if elem == mid_elem:
return mid_row, mid_col
elif up == down and left == right:
return None

if elem > mid_elem:
# Search RIGHT
right_search = search(elem, matrix, up, down, mid_col + 1, right)

if right_search == None:
# Search DOWN
return search(elem, matrix, mid_row + 1, down, left, right)

return right_search

else:
# Search LEFT
left_search = search(elem, matrix, up, down, left, mid_col - 1)

if left_search == None:
# Search UP
return search(elem, matrix, up, mid_row - 1, left, right)

return left_search

return None


The code can be tested with the following:

if __name__ == "__main__":
matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24]]
elem = 8
N = len(matrix)
M = len(matrix[0])
print(search(elem, matrix, 0, N-1, 0, M-1))


I think that my code is pretty neat and easy to understand. As far as I tested it works perfectly, and should have a time complexity similar to the QuadPartition. What I don't understand is why haven't I seen this solution code anywhere? Is there a cleaner and faster way to write it?

• Welcome to Code Review! I hope you get some good answers. Commented Aug 17, 2016 at 2:28

With regards to your code, the only comments I have are that lo and hi may be better names than up and down, and that you probably should have a more specific name than search. As to why you don't see this in the wild, the biggest reason is that Step-wise Linear Search is almost always faster, and simpler to implement. step-wise linear search takes 2n steps to complete, has no recursion, and uses no memory. quad-partitioning, on the other hand, is more complicated, has worse complexity (n^ln(3) vs 2n), and has worse constant factors (due to more branching, and recursion).