Not a bad start, it can eliminate areas. <n <n <n <n ?? ?? ?? ?? <n <n <n <n ?? ?? ?? ?? <n <n <n <n ?? ?? ?? ?? <n <n <n <n ?? ?? ?? ?? ?? ?? ?? ?? >n >n >n >n ?? ?? ?? ?? >n >n >n >n ?? ?? ?? ?? >n >n >n >n
So it would involve searching in the two remaing blocks, recursively until you get an 1xN or Mx1 then a binary search on the row or column. -- Geoff On Nov 25, 3:46 am, Bharath <bharath1...@gmail.com> wrote: > 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 <koushik.infin...@gmail.com > > > > > > > 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 > > Pablo > > Picasso<http://www.brainyquote.com/quotes/authors/p/pablo_picasso.html> - > > "Computers are useless. They can only give you answers." > > > On Tue, Nov 24, 2009 at 7:27 PM, Rohit Saraf > > <rohit.kumar.sa...@gmail.com>wrote: > > >> 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 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<algogeeks%2bunsubscr...@googlegroups.com> > > . > > For more options, visit this group at > >http://groups.google.com/group/algogeeks?hl=en. > > -- > <<Bharath>>- Hide quoted text - > > - Show quoted text - -- 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.
