def problem_9_6(matrix, key):
    """ Given a matrix in which each row and each column is sorted, write a
    method to find an element in it. Matrix is size M*N such that each row is
    sorted left to right and each column is sorted top to bottom.

    Solution: divide and conquer. Start in the top-right and go down and left as
    you narrow down to the searched key.
    """
    m = len(matrix)
    n = len(matrix[0])
    i = 0 # traversed rows.
    j = n - 1 # traverses columns.

    while i < m and j >= 0:
        if key == matrix[i][j]:
            return True
        elif key < matrix[i][j]: # key will be smaller then matrix[..][j]
            j -= 1
        else: # key will larger than matrix[i][...]
            i += 1

    return False