[algogeeks] Re: search a 2d sorted array in less than O(n)
Actual complexity of above algorithm = O(n^1.6)
On Sep 27, 8:19 am, Gene gene.ress...@gmail.com wrote:
If the array is m by n, pick the element a[m/2][n/2], i.e. the one in
the middle. There are now 3 possibilities:
1) The middle element is the one you're looking for, so you're done.
2) The element you're looking for is smaller. In this case you can
throw out about 1/4 of the array: everything right and downward from
a[m/2][n/2] (including row m/2 and column n/2) because these elements
are all larger than the middle one.
3) The element you're looking for is larger. In this case you can
again throw out about 1/4 of the array: everything left and upward
from a[m/2][n/2] inclusive.
Then you can search the remaining 3/4 of the array recursively.
By throwing away 1/4 of mn elements at each step, you can easily work
out the recurrence to see you'll get O(log mn) = O(log(max(m, n)))
performance.
Here is code and a very quick unit test:
#include stdio.h
#include stdlib.h
typedef int SORTED_ARRAY[100][100];
/* Look for x in row- and column-sorted a[i0..i1][j0..j1].
Put indices in *i and *j and return 1 if found,
else return 0.
*/
int search(SORTED_ARRAY a, int x,
int i0, int i1,
int j0, int j1,
int *i, int *j)
{
if (i0 = i1 j0 = j1) {
int mi = (i0 + i1) / 2;
int mj = (j0 + j1) / 2;
if (x == a[mi][mj]) {
*i = mi; *j = mj;
return 1;
}
return (x a[mi][mj]) ?
search(a, x, i0, mi - 1, j0, mj - 1, i, j) ||
search(a, x, i0, mi - 1, mj, j1, i, j) ||
search(a, x, mi, i1, j0, mj - 1, i, j)
:
search(a, x, mi + 1, i1, mj + 1, j1, i, j) ||
search(a, x, i0, mi, mj + 1, j1, i, j) ||
search(a, x, mi + 1, i1, j0, mj, i, j);
}
return 0;
}
int max(int x, int y) { return x y ? x : y; }
int main(void)
{
int i, j, m, n, ri, rj;
SORTED_ARRAY a;
// A small unit test. Build a m x n
// sorted array with random differences.
m = 100; n = 100;
a[0][0] = 0;
for (i = 1; i m; i++)
a[i][0] = a[i - 1][0] + rand() % 1000;
for (j = 1; j n; j++) {
a[0][j] = a[0][j - 1] + rand() % 1000;
for (i = 1; i m; i++)
a[i][j] = max(a[i - 1][j], a[i][j - 1]) + rand() % 1000;
}
for (i = 0; i m; i++) {
for (j = 0; j n; j++) {
printf(%8d, a[i][j]);
}
printf(\n);
}
for (i = 0; i m; i++) {
for (j = 32; j n; j++) {
int r = search(a, a[i][j], 0, m - 1, 0, n - 1, ri, rj);
if (!r) {
printf(failed at a[%d][%d]\n, i, j, a[i][j]);
return 1;
}
else if (a[ri][rj] != a[i][j]) {
printf(mistake at a[%d][%d]=%d: found a[%d][%d]=%d\n,
i, j, a[i][j], ri, rj, a[ri][rj]);
return 1;
}
}
}
printf(pass!\n);
return 0;
}
On Sep 21, 7:40 am, 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.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: search a 2d sorted array in less than O(n)
I feel the binary search approach as given by Saurabh Singh or like
moving from top right row, doing binary search in the row 0, find the
element being searched (say x) or one less than that (say y), followed
by binary search in the column below 'y' and proceeding in this way
can give a less than O(n) solution.
Please provide your comments in any
Thanks
Sourav
On Sep 27, 11:09 am, prodigy 1abhishekshu...@gmail.com wrote:
Actual complexity of above algorithm = O(n^1.6)
On Sep 27, 8:19 am, Gene gene.ress...@gmail.com wrote:
If the array is m by n, pick the element a[m/2][n/2], i.e. the one in
the middle. There are now 3 possibilities:
1) The middle element is the one you're looking for, so you're done.
2) The element you're looking for is smaller. In this case you can
throw out about 1/4 of the array: everything right and downward from
a[m/2][n/2] (including row m/2 and column n/2) because these elements
are all larger than the middle one.
3) The element you're looking for is larger. In this case you can
again throw out about 1/4 of the array: everything left and upward
from a[m/2][n/2] inclusive.
Then you can search the remaining 3/4 of the array recursively.
By throwing away 1/4 of mn elements at each step, you can easily work
out the recurrence to see you'll get O(log mn) = O(log(max(m, n)))
performance.
Here is code and a very quick unit test:
#include stdio.h
#include stdlib.h
typedef int SORTED_ARRAY[100][100];
/* Look for x in row- and column-sorted a[i0..i1][j0..j1].
Put indices in *i and *j and return 1 if found,
else return 0.
*/
int search(SORTED_ARRAY a, int x,
int i0, int i1,
int j0, int j1,
int *i, int *j)
{
if (i0 = i1 j0 = j1) {
int mi = (i0 + i1) / 2;
int mj = (j0 + j1) / 2;
if (x == a[mi][mj]) {
*i = mi; *j = mj;
return 1;
}
return (x a[mi][mj]) ?
search(a, x, i0, mi - 1, j0, mj - 1, i, j) ||
search(a, x, i0, mi - 1, mj, j1, i, j) ||
search(a, x, mi, i1, j0, mj - 1, i, j)
:
search(a, x, mi + 1, i1, mj + 1, j1, i, j) ||
search(a, x, i0, mi, mj + 1, j1, i, j) ||
search(a, x, mi + 1, i1, j0, mj, i, j);
}
return 0;
}
int max(int x, int y) { return x y ? x : y; }
int main(void)
{
int i, j, m, n, ri, rj;
SORTED_ARRAY a;
// A small unit test. Build a m x n
// sorted array with random differences.
m = 100; n = 100;
a[0][0] = 0;
for (i = 1; i m; i++)
a[i][0] = a[i - 1][0] + rand() % 1000;
for (j = 1; j n; j++) {
a[0][j] = a[0][j - 1] + rand() % 1000;
for (i = 1; i m; i++)
a[i][j] = max(a[i - 1][j], a[i][j - 1]) + rand() % 1000;
}
for (i = 0; i m; i++) {
for (j = 0; j n; j++) {
printf(%8d, a[i][j]);
}
printf(\n);
}
for (i = 0; i m; i++) {
for (j = 32; j n; j++) {
int r = search(a, a[i][j], 0, m - 1, 0, n - 1, ri, rj);
if (!r) {
printf(failed at a[%d][%d]\n, i, j, a[i][j]);
return 1;
}
else if (a[ri][rj] != a[i][j]) {
printf(mistake at a[%d][%d]=%d: found a[%d][%d]=%d\n,
i, j, a[i][j], ri, rj, a[ri][rj]);
return 1;
}
}
}
printf(pass!\n);
return 0;
}
On Sep 21, 7:40 am, 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.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: search a 2d sorted array in less than O(n)
Well, friend, we're both wrong. The algorithm will find 6 just fine. It will choose 3 as the middle element. Since 6 is bigger, it will throw away the subarray 1 2 2 3 and check the other 3 subarrays. When it checks 6 7 7 8 It will find the 6 on the first try. I just verified this by running the code. Second, I should have solved the recurrence. You're right that it's ~ n^1.6 . Throwing away a quarter of the _elements_ isn't good enough because that number is n^2. The algorithm is only sublinear in the number of elements, which of course is worse than the standard algorithm that starts at the lower left corner and steps along a jagged path of max length ~2n. But I should have seen that you can split the L-shaped remaining piece of each subarray into only TWO pieces rather than 3. So the recursive calls should have been: return (x a[mi][mj]) ? search(a, x, i0, mi - 1, j0, j1, i, j) || search(a, x, mi, i1, j0, mj - 1, i, j) : search(a, x, i0, mi, mj + 1, j1, i, j) || search(a, x, mi + 1, i1, j0, j1, i, j); With this change the recurrence is more complicated, but it should be faster than n^1.6 . I'm not going to try it tonight... On Sep 27, 8:19 am, Nikhil Jindal fundoon...@yahoo.co.in wrote: @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 athttp://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,
[algogeeks] Re: search a 2d sorted array in less than O(n)
If the array is m by n, pick the element a[m/2][n/2], i.e. the one in
the middle. There are now 3 possibilities:
1) The middle element is the one you're looking for, so you're done.
2) The element you're looking for is smaller. In this case you can
throw out about 1/4 of the array: everything right and downward from
a[m/2][n/2] (including row m/2 and column n/2) because these elements
are all larger than the middle one.
3) The element you're looking for is larger. In this case you can
again throw out about 1/4 of the array: everything left and upward
from a[m/2][n/2] inclusive.
Then you can search the remaining 3/4 of the array recursively.
By throwing away 1/4 of mn elements at each step, you can easily work
out the recurrence to see you'll get O(log mn) = O(log(max(m, n)))
performance.
Here is code and a very quick unit test:
#include stdio.h
#include stdlib.h
typedef int SORTED_ARRAY[100][100];
/* Look for x in row- and column-sorted a[i0..i1][j0..j1].
Put indices in *i and *j and return 1 if found,
else return 0.
*/
int search(SORTED_ARRAY a, int x,
int i0, int i1,
int j0, int j1,
int *i, int *j)
{
if (i0 = i1 j0 = j1) {
int mi = (i0 + i1) / 2;
int mj = (j0 + j1) / 2;
if (x == a[mi][mj]) {
*i = mi; *j = mj;
return 1;
}
return (x a[mi][mj]) ?
search(a, x, i0, mi - 1, j0, mj - 1, i, j) ||
search(a, x, i0, mi - 1, mj, j1, i, j) ||
search(a, x, mi, i1, j0, mj - 1, i, j)
:
search(a, x, mi + 1, i1, mj + 1, j1, i, j) ||
search(a, x, i0, mi, mj + 1, j1, i, j) ||
search(a, x, mi + 1, i1, j0, mj, i, j);
}
return 0;
}
int max(int x, int y) { return x y ? x : y; }
int main(void)
{
int i, j, m, n, ri, rj;
SORTED_ARRAY a;
// A small unit test. Build a m x n
// sorted array with random differences.
m = 100; n = 100;
a[0][0] = 0;
for (i = 1; i m; i++)
a[i][0] = a[i - 1][0] + rand() % 1000;
for (j = 1; j n; j++) {
a[0][j] = a[0][j - 1] + rand() % 1000;
for (i = 1; i m; i++)
a[i][j] = max(a[i - 1][j], a[i][j - 1]) + rand() % 1000;
}
for (i = 0; i m; i++) {
for (j = 0; j n; j++) {
printf(%8d, a[i][j]);
}
printf(\n);
}
for (i = 0; i m; i++) {
for (j = 32; j n; j++) {
int r = search(a, a[i][j], 0, m - 1, 0, n - 1, ri, rj);
if (!r) {
printf(failed at a[%d][%d]\n, i, j, a[i][j]);
return 1;
}
else if (a[ri][rj] != a[i][j]) {
printf(mistake at a[%d][%d]=%d: found a[%d][%d]=%d\n,
i, j, a[i][j], ri, rj, a[ri][rj]);
return 1;
}
}
}
printf(pass!\n);
return 0;
}
On Sep 21, 7:40 am, 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.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
