Here's an O(n) soln: Start from the bottom right corner. Move up within the last column until you reach an element such that the element before that is less than the value being searched and this is greater. Now move left and check for the same. Move one more left. The value can only be in the present column after(below) the element we are on.
At max, 3n moves = O(n). On Sun, Sep 26, 2010 at 7:34 PM, Nikhil Jindal <[email protected]>wrote: > > > On Tue, Sep 21, 2010 at 6:05 PM, saurabh singh <[email protected]>wrote: > >> solution 1: >> use concept of quad-tree and do binary search in that tree >> >> solution 2: >> do binary search on major diagonal. ultimately u will narrow down to >> search for element in 2 rows. in these two rows again do binary search. >> > > How do you narrow down to two rows? Please explain. > By searching on the diagonal, you get two elements such that one is lesser > than the number being searched for and the next is greater. let them be i,i, > and i+1,i+1. > > So you remove the array from 0,0 to i,i and from i+1,i+1 to n-1,n-1. But > the number could be anywhere in the rest of the array > > >> >> any solution will lead you to O(log(n)) time >> >> >> On Tue, Sep 21, 2010 at 5:10 PM, jagadish <[email protected]> wrote: >> >>> Hi all, >>> Given a 2d array which is sorted row wise and column wise as well, >>> find a specific element in it in LESS THAN O(n). >>> PS: an O(n) solution would involve skipping a column or a row each >>> time from the search and moving accordingly. >>> Solution less than O(n) is desirable! >>> >>> -- >>> 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. >>> >>> >> >> >> -- >> Thanks & Regards, >> Saurabh >> >> -- >> 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. >> > > Please access the attached hyperlink for an important electronic communications disclaimer: http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php -- 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.
