Re: [algogeeks] Search in a sorted NxN matrix

it's not similar it's same !! -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more opt

Re: [algogeeks] Search in a sorted NxN matrix

Same applies for this too. 1 2 3 3 5 6 4 7 8 After bsearch on diagonal you are left with (5,6 and 5,7). Do bsearch on this. On Wed, Nov 25, 2009 at 6:27 PM, Bharath wrote: > Bsearch on diagonal elimanates all the submatrix under 9. > > You are left with only one column and a row.Do BinarySearc

Re: [algogeeks] Search in a sorted NxN matrix

Bsearch on diagonal elimanates all the submatrix under 9. You are left with only one column and a row.Do BinarySearch on these lists. On Wed, Nov 25, 2009 at 6:07 PM, chitta koushik wrote: > @Bharath > > I dont think BinSrch on diagnol and then on row works. > Can u explain your algo? chk for t

Re: [algogeeks] Search in a sorted NxN matrix

Arun's idea was what i tried for the nxm version of this problem. And the log(n) wala is not correct for sure. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe f

Re: [algogeeks] Search in a sorted NxN matrix

isnt it similar to youngs tabulaeau as gvn in CLRS On Wed, Nov 25, 2009 at 5:18 PM, Arun wrote: > how about splitting the matrix into 4 squares and considering the rightmost > bottom and comparing it to topmost left corner of each square. in every > iteration you will eliminate atleast one squar

Re: [algogeeks] Search in a sorted NxN matrix

@Bharath I dont think BinSrch on diagnol and then on row works. Can u explain your algo? chk for this matrix 1 2 3 4 5 2 9 12 19 24 3 10 14 18 20 8 13 15 20 23 11 14 16 21 24 Find(8) doesn't give o/p --Koushik C On Wed, Nov 25, 2009 at 5:18 PM, Arun wrote: > how about splitting the m

Re: [algogeeks] Search in a sorted NxN matrix

how about splitting the matrix into 4 squares and considering the rightmost bottom and comparing it to topmost left corner of each square. in every iteration you will eliminate atleast one square. so worst case, you have to repeat this divide and conquer on the three other squares. not good as as b

Re: [algogeeks] Search in a sorted NxN matrix

On Wed, Nov 25, 2009 at 2:16 PM, Bharath wrote: > You can actually do it in O(logn) complexity. Binary Search on diagonal and > then on a row. Will that always work? 1 2 3 3 5 6 4 7 8 Find(6) fails with the usual binary search algorithm. > > > On Tue, Nov 24, 2009 at 10:33 PM, chitta koushik

Re: [algogeeks] Search in a sorted NxN matrix

You can actually do it in O(logn) complexity. Binary Search on diagonal and then on a row. On Tue, Nov 24, 2009 at 10:33 PM, chitta koushik wrote: > Start from top right or bottom left corner and move according if the > element to be searched is lesser or greater than current. > > > --Koushik C

Re: [algogeeks] Search in a sorted NxN matrix

Start from top right or bottom left corner and move according if the element to be searched is lesser or greater than current. --Koushik C Pablo Picasso - "Computers are useless. They can only give you answers." On Tue, Nov 24, 200

[algogeeks] Search in a sorted NxN matrix

A nice problem that i encountered : In O(n) search for a value x in a sorted NxN matrix. Definition of sorted matrix: All rows and all columns are sorted in ascending order. So thought of sharing .. Rohit Saraf Sophomore Computer Science and Engineering IIT Bombay -- You received this message