Last Updated: 10 Jan, 2021
Search in a 2D matrix
Easy
Asked in companies
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
Approaches
The idea is to iterate through the matrix and check if any element is equal to ‘X’.
The steps are as follows :
- Iterate from 0 to ‘N’, let’s say the current index is ‘i’, this will represent our current row.
- Iterate from 0 to ‘M’, let’s say the current index is ‘j’, this will represent the current column of the matrix.
- If arr[i][j] is equal to ‘X’ return true as we have found an element equal to ‘X’.
- Iterate from 0 to ‘M’, let’s say the current index is ‘j’, this will represent the current column of the matrix.
- If there is no element equal to ‘X’ return false.
The idea is to use the property of sorted rows of the matrix and apply binary search on each row.
The steps are as follows :
- Iterate from the 0 to ‘N’, let’s say the current index is ‘i’, this will represent our current row.
- Apply binary search on the current row,
- Initialize “low” to 0 and “high” to M-1, [low, high] will denote our search space.
- Now while low is less than or equal to high do the following,
- Assign a variable “mid” to (low+high)/2.
- If arr[i][mid] is equal to ‘X’ then return true as we have found the element.
- If arr[i][mid] is greater than ‘X’ then change “high” to mid-1 because if ‘X’ is present in the current row then it will only be found at positions smaller than “mid”.
- Else change “low” to “mid+1” because if ‘X’ is present in the current row then it will only be found at positions greater than “mid”.
- If there is no element equal to ‘X’ return false.
The idea is to use the fact that each row is sorted and the first element of each row is greater than the last element of the previous row. We will try to visualize the 2D matrix as a 1D array. The j’th element of the i’th row i.e. arr[i][j] can be represented by giving it an index value of i*M + j. This way each element will have a unique index value and we can apply binary search on the complete matrix.
The steps are as follows :
- Initialize “low” to 0 and “high” to (N-1)*M + M-1, [low,high] will denote our search space.
- Now while low is less than or equal to high do the following,
- Assign a variable “mid” to (low+high)/2.
- The row number of “mid” element can be determined by floor(mid/M) and the column number can be determined by (mid%M), let’s denote the row and the column number by “row” and “col” respectively.
- If arr[row][col] is equal to ‘X’ then return true as we have found the element.
- If arr[row][col] is greater than ‘X’ then change “high” to mid-1 because if ‘X’ is present in the given matrix then it will only be found at positions smaller than “mid”.
- Else change “low” to “mid+1” because if ‘X’ is present in the given matrix then it will only be found at positions greater than “mid”.
- If there is no element equal to ‘X’ return false.