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 binary search though(in the sense of eliminating 2 squares).
On Wed, Nov 25, 2009 at 3:12 AM, Aditya Shankar < iitm.adityashan...@gmail.com> wrote: > > > On Wed, Nov 25, 2009 at 2:16 PM, Bharath <bharath1...@gmail.com> 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 < >> 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>> >> >> >> -- >> 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. > -- 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.
