Search in a Sorted 2D Matrix

In this article, we will be solving a 2D array search problem. So we are given a matrix of size N x M, where N and M represent the number of rows and columns, respectively. The elements in every row are sorted and the first element of every new row is greater than the last element of the previous row So our task is to find whether an integer target is present in the matrix.

Example:

1 3 5

7 9 11

13 15 17

Target = 9 Output: Yes

Target = 6 Output: No

Solution:

Explanation:

·       The binarySearchRow function performs a binary search on a given row to find the target.

·       The left and right are initialized as the start and end indices of the row and mid is the middle index.

·       If row[mid] equals the target, return true. If row[mid] is less than the target, move left to mid + 1 else move right to mid - 1.

·       The function searchInMatrix is used to search the target in the matrix. The numRows and numCols are initialized as the number of rows and columns in the matrix.

·       We then iterate over each row in the matrix and check if the target is within the range of the first and last elements of the row.

·       If the target is within this range, call binarySearchRow to perform a binary search on that row.

·       If the target is found, return true else return false.

Time Complexity: O(NlogM)

Space Complexity: O(1)