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