let i be in 1,n^2
use bisection on that interval taking i%n and i/n to access the matrix
and check the bisection condition.
On Aug 20, 4:42 pm, Dufus rahul.dev.si...@gmail.com wrote:
AFAIK, searching an element in sorted matrix (Young's Tableau) takes O
(n) time.
So I am not sure if
If it is o(n) only then we can do a normal search. But data is sorted
left and down so how to use this property.
On Thu, Aug 20, 2009 at 8:12 PM, Dufusrahul.dev.si...@gmail.com wrote:
AFAIK, searching an element in sorted matrix (Young's Tableau) takes O
(n) time.
So I am not sure if O(logn)
A more general problem is discussed in Introduction to Algorithms by
Cormen et al
problem 6-3, although the running time is O(n)...
nagendra kumar wrote:
How can we find an element in the matrix [n*n] which is sorted row
wise and column wise in O(log n).
I guess it is famous Younge Tableau Problem of tableau MxN and searching
can be done in O(M+N).
I doubt the problem can be solved in O(lgn) if no space constraint and no
pre-processing constraint present.
On Thu, Aug 20, 2009 at 9:42 PM, Anil C R cr.a...@gmail.com wrote:
A more general problem
i can improve a bit..
my logic is that
i will take the a[n/2][n/2] element (middle of the diagonal element)
if (num_2_b_search a[n/2][n/2])
square sub matrix from a[0][0] till a[n/2][n/2] can be left out..
i mean divide the whole matrix in 4 half
A B
C D
in my above case
A is chopped off
@pramod
yeh u r rite..
On Thu, Aug 20, 2009 at 10:20 PM, Pramod Negi negi.1...@gmail.com wrote:
I guess it is famous Younge Tableau Problem of tableau MxN and searching
can be done in O(M+N).
I doubt the problem can be solved in O(lgn) if no space constraint and no
pre-processing
i can improve a bit to
O(n^(log 3 base4 ))
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group,
AFAIK, searching an element in sorted matrix (Young's Tableau) takes O
(n) time.
So I am not sure if O(logn) is actually possible.
_dufus
On Aug 20, 6:41 pm, nagendra kumar nagendra@gmail.com wrote:
How can we find an element in the matrix [n*n] which is sorted row
wise and column wise
