A Python version of "search a sorted matrix faster" as seen in http://twistedoakstudios.com/blog/Post5365_searching-a-sorted-matrix-faster http://stackoverflow.com/a/2468729/500584 and https://news.ycombinator.com/item?id=6205274

search_sorted_matrix.py

class TransposedMatrix(object):
    def __init__(self, matrix, index = None):
        self.matrix = matrix
        self.index = index

    def __getitem__(self, index):
        if self.index is None:
            return TransposedMatrix(self.matrix, index)
        return self.matrix[index][self.index]

    def __len__(self):
        if self.index is None:
            return len(self.matrix[0])
        return len(self.matrix)

def search_sorted_matrix(matrix, target, key = lambda x: x):
    """
    >>> example = [[1, 2, 3, 4, 5],
    ...            [1, 2, 3, 5, 7],
    ...            [1, 4, 9, 16, 25]]
    >>> search_sorted_matrix(example, 0)
    >>> search_sorted_matrix(example, 1)
    (0, 0)
    >>> search_sorted_matrix(example, 2)
    (0, 1)
    >>> search_sorted_matrix(example, 3)
    (0, 2)
    >>> search_sorted_matrix(example, 4)
    (0, 3)
    >>> search_sorted_matrix(example, 5)
    (0, 4)
    >>> search_sorted_matrix(example, 7)
    (1, 4)
    >>> search_sorted_matrix(example, 9)
    (2, 2)
    >>> search_sorted_matrix(example, 16)
    (2, 3)
    >>> search_sorted_matrix(example, 25)
    (2, 4)
    >>> example = zip(*example)
    >>> search_sorted_matrix(example, 0)
    >>> search_sorted_matrix(example, 1)
    (0, 0)
    >>> search_sorted_matrix(example, 2)
    (1, 0)
    >>> search_sorted_matrix(example, 3)
    (2, 0)
    >>> search_sorted_matrix(example, 4)
    (3, 0)
    >>> search_sorted_matrix(example, 5)
    (4, 0)
    >>> search_sorted_matrix(example, 7)
    (4, 1)
    >>> search_sorted_matrix(example, 9)
    (2, 2)
    >>> search_sorted_matrix(example, 16)
    (3, 2)
    >>> search_sorted_matrix(example, 25)
    (4, 2)
    """

    width = len(matrix)
    height = len(matrix[0])

    if height < width:
        result = search_sorted_matrix(TransposedMatrix(matrix), target)
        return result and result[::-1]

    min_col = 0
    max_row = height - 1
    t = height // width

    while min_col < width and max_row >= 0:
        row = max(max_row - t, 0)
        value = key(matrix[min_col][row])
        if target == value:
            return min_col, row
        if target < value:
            max_row = row - 1
            continue

        min_row = row + 1
        while min_row <= max_row:
            row = min_row + (max_row - min_row + 1) // 2
            value = key(matrix[min_col][row])
            if target == value:
                return min_col, row
            if target < value:
                max_row = row - 1
            else:
                min_row = row + 1

        min_col += 1

if __name__ == "__main__":
    import doctest
    doctest.testmod()