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.
