@mac, Nice solution! On Fri, Dec 24, 2010 at 7:13 PM, MAC <macatad...@gmail.com> wrote:
> move from top rightmost column , go down if the number being searched is > greater or left if the number being seracehd is small .. O(m+n) > > if u wanted to search 5 , u start from 3 (top right) , and since 5>3 , u go > down to 4 , then 5 >4 so go down , u reach 6 . now 5 <6 so u will need to go > left .. till u find 5 or less than 5 > > hope this helps > > regards > --mac > > > On Sat, Dec 25, 2010 at 8:25 AM, yq Zhang <zhangyunq...@gmail.com> wrote: > >> Suppose you have a matrix n*m. each column and row of the matrix is >> already sorted. For example: >> >> 1,2,3 >> 2,3,4 >> 4,5,6 >> >> All 3 rows and 3 columns of above matrix are sorted. How to find a >> specific number in the matrix? >> The trivial O(nlogm) solution is to use binary search for all rows. I >> am looking for better solution. >> >> Thanks >> >> -- >> 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<algogeeks%2bunsubscr...@googlegroups.com> >> . >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> >> > > > -- > thanks > --mac > > -- > 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<algogeeks%2bunsubscr...@googlegroups.com> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- 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 options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
