You are given a 2-dimensional integer array A of size (n times n) and told that
ID: 3886737 • Letter: Y
Question
You are given a 2-dimensional integer array A of size (n times n) and told that The integers in each row are in increasing order, and The integers in each column are in increasing order. An example of such an arrangement (n a smaller scale) is shown below 1 7 9 14 19 6 18 21 26 29 11 24 28 42 44 20 32 37 47 52 31 49 61 72 99 Your task is to search for a given integer x. (a) How many steps would it take if you perform a binary search of the elements starting from the top row and ending in the bottom row? Use the Big-O notation to matrix of size (n times n). Answer. (b) How would you use the ordering of the rows and columns of A to "speed up" your search for x? Present your high-level idea in two sentences.Explanation / Answer
The basic idea comes in my mind is -
for(i=0;i<c;i++)
{
for(j=0;j<r;j++)
{
if(a[i][j]==element)
{
printf "element is found";
exit(0);
}
}
}
print "Element not found"
.
But here the time coplexity will be O(n2) and (i+1)*(j+1) steps will be executed .
(a)if we perform binary search only on rows or columns then the complexity is O(n*log(n)) , logn for binary search and n for either rows or columns.
int search(int a[][], int n, int x)
/* n is the number of rows or columns in matrix and x is the element to be searched */
{
int i = 0, j = n-1; //the first index is set to top of the right side element
while ( i < n && j >= 0 )//single loop
{
if ( a[i][j] == x )//constant time execution
{
printf("element is found at index %d, %d", i, j);
return 1;
}
if ( a[i][j] > x )
j--;
else
// if a[i][j] < x
i++;
}
printf("Element not found");
return 0; // if ( i==n || j== -1 )
}
This is the efficient solution and it runs in linear time complexity so time complexity = O(n)
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.