Suppose that you are given an m*n grid of integers where each row and each colum

Question

Suppose that you are given an m*n grid of integers where each row and each column are in sorted order (we'll call this a sorted grid). For example:

10 12 13 21 32 34 43 51 67 69 90 101 133

16 21 23 26 40 54 65 67 68 71 99 110 150

21 23 31 33 54 58 74 77 97 98 110 111 150

32 46 59 65 74 88 99 103 113 125 137 149 159

53 75 96 115 124 131 132 136 140 156156 157 161

84 86 98 145 146 151 173 187 192 205 206 208 219

135 141 153 165 174181 194 208 210 223 236 249 258

216 220 222 225 234 301 355 409 418 446 454 460 541

Design an O(m + n)-time algorithm that, given as input a sorted m n grid and an integer, returns whether or not that integer is contained in the grid. Your algorithm should use only O(1) additional space. Then: Describe your algorithm. Prove that your algorithm is correct. Prove that your algorithm runs in time O(m + n) and uses O(1) additional space.

Explanation / Answer

The algorithm is given below.

ALGORITHM:

Below is the code in C++.

CODE

===================

// C++ program to search an element in row-wise

// and column-wise sorted matrix

#include <bits/stdc++.h>

using namespace std;

/* Searches the element x in mat[][]. If the

element is found, then prints its position

and returns true, otherwise prints "not found"

and returns false */

int search(int mat[4][4], int n, int x)

{

int i = 0, j = n-1; //set indexes for top right element

while ( i < n && j >= 0 )

{

    if ( mat[i][j] == x )

    {

        cout << "n Found at "

            << i << ", " << j;

        return 1;

    }

    if (mat[i][j] > x )

        j--;

    else // if mat[i][j] < x

        i++;

}

cout << "n Element not found";

return 0; // if ( i==n || j== -1 )

}

// Driver code

int main()

{

int mat[4][4] = { {10, 20, 30, 40},

                    {15, 25, 35, 45},

                    {27, 29, 37, 48},

                    {32, 33, 39, 50}};

search(mat, 4, 29);

return 0;

}

Time complexity: O(m+n)

Space Complexity: O(1)

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.