You are given an n by n matrix of distinct integers such tha

You are given an n by n matrix of distinct integers such that all rows and all columns are increasing. So, every row read left to right is an increasing sequence of integers and every column read from top to bottom is an increasing sequence of integers. You would like to determine if a given integer k is in the matrix. You can access any entry of the matrix (it costs one unit of time to compare two different entries of the matrix). Come up with a ”divide and conquer” algorithm that solves this problem by splitting the matrix into quadrants. Explain why your algorithm is correct. Write a recurrence for the running time of this algorithm. Determine the Big-O time complexity of this algorithm. For full credit your algorithm should beat the obvious (n2) time complexity. For bonus credit, give an O(n) time algorithm.

Solution

//Algorithm:

In n*n matrix start at right most corner i.e, A[0][n-1] if k < A[0][n-1] implies k will not be in nth column since A[0][n-1] is least element in nth column similarly if k > A[0][n-1] k doesn\'t belong to first row because A[0][n-1] is largest element in first row.if k < A[0][n-1] go to right top corner of array without Nth column because we eliminated it similarly if k > A[0][n-1] go to right top corner of matrix without firsi row .

//COMPLEXITY:

Since in each comparison we\'re eliminating either a row or a column matrix will searched in O(n) time.

//CODE:

#include<iostream>
using namespace std;
bool findk(int k,int ***A,int n)
{
   int **B = *A,i=0,j=n-1;
   while(i!=n && j != -1) //termination condition either all rows or columns are eliminated
   {
       if(k == B[i][j])//if number is found return true
           return true;
       if(k > B[i][j])//elimination of row since element > largest element of row
       {
           i++;
           continue;
       }
       if(k < B[i][j])//elimination of column since element < smallest element of column
       {
           j--;
           continue;
       }
  
   }
   return false;//not found so return false
}
int main()
{
   cout<<\"Enter Size of Array:\"<<endl;
   int N,a,k;
   cin>>N;//input for N
   int **A;//declaring array of size N
   A=new int* [N];
   for (int i=0;i<N;i++)
   {
       A[i] = new int[N]; //declaring 2D matrix dynamically
       cout<<\"Enter row: \"<<i<<endl;
       for (int j=0;j<N;j++)
           cin>>A[i][j]; //taking input of matrix should be in order according to question
   }
   while(true)//infinite loop for performing queries
   {
       cout<<\"Enter 1 to search for a number\ else to exit\"<<endl;
       cin>>a;
       if(a==1)
       {
           cout<<\"Enter Number to search for:\"<<endl;
           cin>>k;
           cout<<\"Number \"<<k<<\"\'s presence is \"<<findk(k,&A,N)<<endl;//function call findk 0 implies not found and 1 implies found
       }
       else
       {
           break;//exiting
       }
  
   }
   return 0;
}

//OUTPUT:

09:45:39@Chegg$g++ sorted_find.cpp
09:49:56@Chegg$./a.out
Enter Size of Array:
3
Enter row: 0
1 2 3
Enter row: 1
4 5 9
Enter row: 2
7 8 9
Enter 1 to search for a number
else to exit
1
Enter Number to search for:
1
Number 1\'s presence is 1
Enter 1 to search for a number
else to exit
1
Enter Number to search for:
4
Number 4\'s presence is 1
Enter 1 to search for a number
else to exit
1
Enter Number to search for:
11
Number 11\'s presence is 0
Enter 1 to search for a number
else to exit