Binary Search on Matrix
0% completed
Search in Rotated Sorted Array
Search in a 2-D Matrix
Search in a 2-D Matrix II
First and Last Position of an element in sorted array
Occurrence of x in a sorted array 1

# Search in a 2D matrix

Difficulty: EASY

Problem Statement
Suggest Edit

#### You are given a 2-D matrix with 'N' rows and 'M' columns, each row of the matrix is sorted in non-decreasing order and the first element of each row is greater than or equal to the last element of the previous row. You are also given an integer ‘X’, you are supposed to find whether 'X' is present in the given matrix or not.

##### Input Format :
``````The first line contains a single integer ‘T’ denoting the number of test cases. The test cases are as follows.

The first line of each test case contains three integers ‘X’, ‘N’ and ‘M’ separated by a single space denoting the element to be searched, the number of rows in the matrix, and the number of columns in the matrix respectively.

The next ‘N’ lines contain ‘M’ integers each denoting the elements of the matrix.
``````
##### Output Format :
``````For each test case, print “Yes”(without quotes) if ‘X’ is present in the matrix otherwise print “No”.

Print the output of each test case on a new line.
``````
##### Note :
``````You don’t need to print anything; It has already been taken care of.
``````
##### Constraints :
``````1 <= T <= 50
1 <= X <= 10 ^ 6
1 <= N, M <= 100
-10 ^ 6 <= ARR[i][j] <= 10 ^ 6

Where ‘T’ denotes the number of test cases, ‘N’ denotes the number of rows in a matrix, ‘M’ denotes the number of columns in the matrix and ARR[i][j] denotes the j-th element of the i’th row of the given matrix.

Time Limit: 1 sec
``````
##### Sample Input 1 :
``````2
4 2 2
2 4
8 12
7 3 4
1 2 4 5
8 12 14 16
23 25 26 29
``````
##### Sample Output 1 :
``````Yes
No
``````
##### Explanation of Sample Input 1 :
``````In the first test case, the 2nd element of the first row is equal to 4, hence the output is “Yes”.

In the second test case, 7 is not present in the matrix hence the output is “No”.
``````
##### Sample Input 2 :
``````2
2 1 1
2
22 3 2
3 4
11 17
23 27
``````
##### Sample Output 2 :
``````Yes
No
``````
##### Explanation of Sample Input 2 :
``````In the first test case, the only element is equal to 2, hence the output is “Yes”.

In the second test case, 22 is not present in the matrix hence the output is “No”.
``````   Console