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.
