[agf]

I wrote a version in Python: https://gist.github.com/agfor/6225437

The original code can be used under CC BY-SA 3.0 since it was posted on Stack Overflow: http://stackoverflow.com/a/2468729/500584

[Strilanc]

Nice.

Small clarification, you have this:

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

Does zip(* matrix) complete in constant time, or time proportional to w*h? I was only able to get away with transposing because I used a LazyTranpose method that finished in constant time and added only constant overhead to each access.

I noticed that you noticed col_max_row was redundant with max_row. I was wondering if anyone would. (It used to not be, when I wasn't taking advantage of eliminating rows during the binary search. It made the animations look really dumb, so I fixed that but didn't notice the redundancy.)

Oh, lastly, some of your tests are brittle. search_sorted_matrix(example, 1) is not required to return (0, 0). Tweaking the implementation could conceivable change that to (0,1) or (0, 2). What's important is that M[result] == query.

[agf]

Yeah, zip is w*h. I meant to replace it once everything was working but forgot. It's simple to write a "TransposedMatrix" wrapper that only adds constant overhead:

  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)

and I've updated the gist to do that. Thanks for pointing it out.

The tests are definitely quick & dirty; I'm aware there can be more than one correct answer.