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

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

  • \$\begingroup\$ Welcome to Code Review! I hope you get some good answers. \$\endgroup\$ – Phrancis Aug 17 '16 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).

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.