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 &gt; down or right &lt; 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 &gt; 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?
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).