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 < [email protected]> wrote: > > > On Wed, Nov 25, 2009 at 2:16 PM, Bharath <[email protected]> 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 < >> [email protected]> 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 < >>> [email protected]> 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 [email protected]. >>>> To unsubscribe from this group, send email to >>>> [email protected]<algogeeks%[email protected]> >>>> . >>>> 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 [email protected]. >>> To unsubscribe from this group, send email to >>> [email protected]<algogeeks%[email protected]> >>> . >>> 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 [email protected]. >> To unsubscribe from this group, send email to >> [email protected]<algogeeks%[email protected]> >> . >> 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 [email protected]. > To unsubscribe from this group, send email to > [email protected]<algogeeks%[email protected]> > . > 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 [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
