Properties of adjacent submatrixes [closed]

Question

Hi! I've encountered a matrix problem when designing an algorithm, which I cannot seem to figure out. I have a (square) matrix with the following properties:

j<k → a_ij<a_ik, a_ji<a_ki
a_ij≠a_kl unless i=k, j=l

That is, elements are strictly increasing along rows and columns, and all elements are unique.

Now, I want to do a fast search for an element in this matrix. So I divide it into four square submatrixes of 1/4 the size (taking care of odd size if needed). My thinking is that the interval of elements in a given submatrix is bounded by the upper left and lower right elements.

$\left(\begin{array}{ccccc} a_{11} & a_{12} & | & a_{13} & a_{14} \\\\ a_{21} & a_{22} & | & a_{23} & a_{24} \\\\ -&-&+&-&- \\\\ a_{31} & a_{32} & | & a_{33} & a_{34} \\\\ a_{41} & a_{42} & | & a_{43} & a_{44} \\\\ \end{array}\right)$

So, in this example (I can't get the array environ to draw lines, so it looks kinda ugly), I'd check interval a11 to a22, then a13 to a24, a31 to a42 and a33 to a44, and then recursivly checking until the size of the submatrix is 1x1.

My intuition tells me I would at most have to check two submatrixes at any step (ie there are at most two intervals which could contain a given number). However, I can only seem to prove that there are at most three. Am I wrong, and this is the best possible?

Answer 1

Note that even if you could eliminate two of the submatrices at each step, you would be left with a Θ(N^1/2) algorithm (where N=n*n is the total number of entries in the matrix). Fortunately, there's a simple Θ(N^1/2) algorithm anyway:

def search(item):
    (i, j) = (0, n-1);
    while i < n and j >= 0:
        if a[i,j] == item:
            return (i,j)
        else if a[i,j] > item:
            j = j-1
        else 
            i = i+1
    return Not_Found;

I'm not sure it's the fastest possible, but it's probably at least as good as whatever you were trying.

Answer 2

Nevermind, came up with a counterexample. (Trivial too, disheartenly enough :( ) One cannot assume that there will be at most two submatrixes with the sought interval. It can be seen by assigning a large value for a_22, and smallest possible values for the first row and column. Then, there will be numbers such that it lies in the intervals of all submatrixes but the lower right one.