Searching a Sorted Matrix Faster
twistedoakstudios.com
twistedoakstudios.com
A minor quibble - it is very difficult to find a paradigm in which the running time of the proposed algorithm differs from simply choosing the best of the obvious algorithms.
Line at a time takes O( max(w,h) ). Binary searching each row and column separately takes O( min(w,h) log(max(w,h) ). Therefore, implementing both basic algorithms and using the faster one at run-time will run in time O(min(max(w,h), min(w,h)log(max(w,h)).
Which is very close to the proposed run-time - unfortunately so much so that it is very hard to find a sequence of (w,h) for which the proposed algorithm works asymptotically better than simply doing "the obvious thing".
But it is possible! And the lower bounds are nice!
let w = n/log(n)
let h = n
(Note: I use ↑ and ↓ as binary operators for max and min.)
(Note: @= means asymptotically equal. Analogous for @<.)
'switching'
@= (w ↑ h) ↓ ((w ↓ h) log(w ↑ h))
@= (n/log(n) ↑ n) ↓ ((n/log(n) ↓ n) log(n/log(n) ↑ n))
@= n ↓ (n/log(n) log(n))
@= n
'lower'
@= ((w ↓ h) log((w ↑ h)/(w ↓ h))
@= n/log(n) log(n/(n/log(n))
@= n log(log(n)) / log(n)
@< nThe original code can be used under CC BY-SA 3.0 since it was posted on Stack Overflow: http://stackoverflow.com/a/2468729/500584
Small clarification, you have this:
if height < width:
result = search_sorted_matrix(zip(*matrix), target)
return result and result[::-1]
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.
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)
The tests are definitely quick & dirty; I'm aware there can be more than one correct answer.
I wrote on another problem that uses this technique. Mix ternary search and linear search to find the minima of an first decreasing then increasing array.
http://www.chaoxuprime.com/posts/2013-07-27-find-the-minimum...
How? That is an algorithm for a completely different problem, which is not obviously reducible to this one.