Re: [algogeeks] search a 2d sorted array in less than O(n)
Trivial algorithm : (Assuming it is in ascending order in both columns and rows) logarithmic time in max(n,m) Divide the 2-d table to 4 parts, the -right-bottom-most and the left-bottom-most are the smallest and largest values in the subtable. It should be clear that atleast two subtables can be rejected straightforward from just this info. Hence the complexity T(m,n) = 2 * T(m/4,n/4) + c Rohit Saraf Third Year Undergraduate Compter Science 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. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] search a 2d sorted array in less than O(n)
Thanks for pointing out. I was wrong because I assumed that numbers would be in continuous increasing order when numbers in each row are written in a line taking each row at a time. On Mon, Sep 27, 2010 at 5:49 PM, Nikhil Jindal fundoon...@yahoo.co.inwrote: @saurabh.nsit: Consider the following array: 1 2 6 7 2 3 7 8 4 5 8 9 5 7 9 10 And the item to be searched is 6. As I understand it, using your approach you will search 6 in only the second and third row, which will not give the correct solution. Hope this clears a few doubts. @Gene: Analysing the complexity of ur algo: T(n) = 3*T(n/2) + O(1) which is n^(log_2(3)) = n^1.6. Cheers Nikhil Jindal On Sun, Sep 26, 2010 at 11:14 PM, saurabh singh saurabh.n...@gmail.comwrote: As you mentioned ultimately element to be searched should either be in row 'i' (ahead of [i,i] element) or in row i+1 (before [i+1,i+1] element). Since each row contain numbers in sorted order so u can do binary search on these two rows and ultimately the complexity will be O(logn) only On Sun, Sep 26, 2010 at 7:34 PM, Nikhil Jindal fundoon...@yahoo.co.inwrote: On Tue, Sep 21, 2010 at 6:05 PM, saurabh singh saurabh.n...@gmail.comwrote: 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 jagadish1...@gmail.comwrote: 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . 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 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 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . 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 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 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 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.
Re: [algogeeks] search a 2d sorted array in less than O(n)
On Tue, Sep 21, 2010 at 6:05 PM, saurabh singh saurabh.n...@gmail.comwrote: 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 jagadish1...@gmail.com 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . 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 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.
Re: [algogeeks] search a 2d sorted array in less than O(n)
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 fundoon...@yahoo.co.inwrote: On Tue, Sep 21, 2010 at 6:05 PM, saurabh singh saurabh.n...@gmail.comwrote: 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 jagadish1...@gmail.com 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . 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 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.
Re: [algogeeks] search a 2d sorted array in less than O(n)
Sorry the last solution wont work.
Here's the correct O(n) soln:
Start from top-right element.
If it is greater than the item, go left.
Else go down.
Keep on doing this until you find the element or can not go left or down
(then the element is not in the array).
void 2dsearch(int i, int j, int item)
{
if (i0 || j0 || in-1 || jn-1)
{
printf(Not Found\n);
return;
}
if( a[i][j] == item) printf(Found: %d %d\n, i, j);
elseif( a[i][j] item) 2dsearch(i, j-1, item);
else 2dsearch(i+1, j, item);
}
Call this function as 2dsearch(0, n-1, item);
Cheers
Nikhil Jindal
Delhi College of Engineering
On Sun, Sep 26, 2010 at 8:06 PM, Nikhil Jindal fundoon...@yahoo.co.inwrote:
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 fundoon...@yahoo.co.inwrote:
On Tue, Sep 21, 2010 at 6:05 PM, saurabh singh saurabh.n...@gmail.comwrote:
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 jagadish1...@gmail.comwrote:
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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
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 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.
Re: [algogeeks] search a 2d sorted array in less than O(n)
As you mentioned ultimately element to be searched should either be in row 'i' (ahead of [i,i] element) or in row i+1 (before [i+1,i+1] element). Since each row contain numbers in sorted order so u can do binary search on these two rows and ultimately the complexity will be O(logn) only On Sun, Sep 26, 2010 at 7:34 PM, Nikhil Jindal fundoon...@yahoo.co.inwrote: On Tue, Sep 21, 2010 at 6:05 PM, saurabh singh saurabh.n...@gmail.comwrote: 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 jagadish1...@gmail.com 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . 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 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 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 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.
[algogeeks] search a 2d sorted array in less than O(n)
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 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.
Re: [algogeeks] search a 2d sorted array in less than O(n)
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. any solution will lead you to O(log(n)) time On Tue, Sep 21, 2010 at 5:10 PM, jagadish jagadish1...@gmail.com 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . 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 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.
