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 <[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].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
