Search in sorted matrix NxM

Question

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?

• Phrancis: Welcome to Code Review! I hope you get some good answers.

Answer 1

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).