Given an n x n matrix of integers sorted vertically and horizontally
in non-decreasing order. What is the fastest time algortihm to do a
search for a given value? Include proof that the time is optimal

---

Request for Question Clarification by maniac-ga on 05 Oct 2003 15:59 PDT

Hello Bearcat11,

Hmm. An odd way to pose the question.

Let's say we have a 3 x 3 matrix, with values

   1  10  20
  30  55  72
100 160 225

How is this different than finding a given value of 
1 10 20 30 55 72 100 160 225
which I would use a method such as a binary search?

If the numbers are ordered in some other way or other constraints, can
you describe it for us?
  --Maniac

---

Clarification of Question by bearcat11-ga on 07 Oct 2003 11:25 PDT

yes, the problem is only to search for the presence of a given
integer. How many times it is present as in the case of an integer
that appears more than once is not important

---

Request for Question Clarification by mathtalk-ga on 08 Oct 2003 08:36 PDT

Hi, bearcat11-ga:

I can provide proofs that the complexity is between n and n(1 + lg n)
and point you to a paper which describes optimal algorithms for this
type of problem.  The paper proves that the complexity O(n) is optimal
and is available to download from the Web.

Would that be satisfactory?

regards, mathtalk-ga

---

Clarification of Question by bearcat11-ga on 08 Oct 2003 19:35 PDT

ok, that is satisfactory

---

Request for Question Clarification by mathtalk-ga on 10 Oct 2003 14:08 PDT

Hi, bearcat11:

Just to let you know, the link to the paper (in compressed PostScript
format) on the Web doesn't seem to be working.  I don't want to give
an incomplete answer, so I'll try to hit the university library in the
morning to get you a better write-up than the meager info in the
paper's abstract.

regards, mathtalk

---

Clarification of Question by bearcat11-ga on 13 Oct 2003 05:39 PDT

If there is an answer coming to this, I need it by 1:00 pm PDT on
Monday October 13th.

Thanks

---

Request for Question Clarification by mathtalk-ga on 14 Oct 2003 06:04 PDT

Sorry, Bearcat11.  The answer is 2n-1 comparisons are needed (in the
worst case).  I have a proof, references, etc.  For future reference,
if a deadline is involved, it's best to let the researchers know about
this.  Otherwise I tend to wait until I have the best answer possible.
 In this case I made two trips to the library and consulted my own
copy of Knuth's Art of Computer Programming v.3 (Sorting and
Searching) before I felt my answer was complete.

Since your deadline is now past, I will not post an answer unless you
specifically request it.

regards, mathtalk-ga

---

Request for Question Clarification by mathtalk-ga on 17 Oct 2003 07:44 PDT

Hi, Bearcat11:

When you no longer want an answer to a question, you can use the
"Close" button at the upper right of the Web page (only the question
poster, you, can view this).  Of course if you are still interested in
receiving Comments, but not an Answer, you may want to leave it open,
but there's always a slight risk that a well-meaning Researcher may
post an Answer without realizing from your clarifications that it is
no longer wanted.  The guidelines recommend closing the question in
this case, to prevent that.

The question will "naturally" expire on Nov. 4th, which is more than
two weeks away.

regards, mathtalk-ga

I think the asker meant that the numbers in each column, when written
out, will be in order, as well as the number in each row.  Thus, under
this scheme this matrix is legal:
  1    10    20
  5    20    24
  7    21    25

secret901-ga

The best algorythm will depend on the size of the matrix, and whether
or not there is any structure to the data other than the fact that
they are "in non-decreasing order".  It would also depend on whether
you want to do a single search, or if you are going to repeatably
search the matrix.  For example, if you were going to search the
matrix thousands of times, then perhaps it might be best to first
index the matrix.  However, if you were only going to search it once,
and it were in random order, then you might as well just loop from the
start to the end until you find what you are looking for.

_Carl.

Yes, the matirx could be ordered as this one posted by secret901 is.
So if the original comment was to take the numbers and put them in a
single array in order to do a binary search, you'd have to do some
extra sorting because, as in this example, the array would not
necessarily be sorted if you just laid them out in a one dimensional
array.
 I will add one more caveat. The n is a multiple of 2, so you will
have a 2 x2 , a 4 x 4, an 8 x 8 ,etc martix which will allow for the
matrix to be sub-divided into four quadrants to allow for a divide and
conquer strategy, if that is the best alternative.
  As for the last comment, I am only looking for the time for a single
search, but I am definitley looking for a better running time than an
algorithm that just does a sequential search on every element until
the correct one is found.

Thanks,
bearcat11

I'm interpreting the problem as asking whether or not a given value is
present.  The variant problem to locate all such matches may be harder
(in the sense of requiring more steps).

A lower bound on (worst case) complexity is n comparisons.

An upper bound is n(1 + lg n) comparisons.

regards, mathtalk-ga