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.