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

StackExchange Code Review Q#138893, answer score: 2