#include

#include

#include

#include

#define N $10$

#define M $10$

using namespace std;

$//$ Function to create a sorted matrix.

$//$ You don't need to modify or understand this $($just don't waste time$)$

std::vector$$ vector $>$ createSortedMatrix$()$

$\{$

std::vector$$ vector $>$ matrix$($N$)$;

std::vector row$($M$)$;

int i$,$j$,$n;

srand$($time$($NULL$))$;

for $($i$=0$;i $>$ m$)$

$\{$

for $($int i$=0$;i $($write your answer HERE!$)$

$*/$

bool searchNum$($vector$$ vector $>$ m$,$ int e$)$

$\{$

$//*********$

$//$ Write your solution here for Question $1.$

$//*********$

$\}$

$//$ You don't need to change the main function.

int main$()$

$\{$

std::vector$$ vector $>$ matrix$($N$)$;

int e;

matrix $=$ createSortedMatrix$()$;

printSortedMatrix$($matrix$)$;

std::cout $$ "Element to search for : $"$;Q$1)$ Sorted Matrix $($definition$)$: in a sorted matrix of size NxM$,$ elements in each row is

sorted in ascending order and the first number of each row is greater than the last

number of the previous row.

You are required to implement an efficient algorithm to search a given number, $k,$ in

a sorted matrix. We already know that the common method of searching for an

element in a matrix involves scanning the entire matrix, and thus, this approach has

a time complexity of $O(NM).$ The algorithm you will develop should offer a better

solution than this $($Do NOT code the classical matrix search algorithm$).$

$($Hint: think about the well$-$known efficient method for searching an item in a sorted

array. Using this algorithm, you should first locate the correct row; then look for the

element in that row of the sorted matrix$).$

You are given the empty function body and a driver program $($Q$1.$cpp$),$ which a

sample sorted matrix $($of type vector $$ vector $$ int $>>)$ is already created and printed

for you.

a$)$ Implement your proposed search algorithm within the body of the given function.

b$)$ Analyze your code and determine time complexity with respect to $N$ and $M($write

your answer right above the function$)$

std:cin $>>$ e;

bool result $=$ searchNum$($matrix$,$e$)$;

if $($result$)$

cout $$ e is found in the matrix!";

else

cout $$ e is NOT found";

return $0$;

$\}$