Intermediate Level
Implement the searchSortedMatrix method that checks whether the target exists in a sorted matrix.
The input contains a sorted matrix, its rows and cols, and a target value.
Each row is sorted in ascending order, and the matrix can be searched like one sorted list when rows continue in increasing order.
Your task is to return true if the target exists in the matrix, otherwise return false.
Example 1
Input
matrix (int[][]) =
[[1,3,5],[7,9,11]]rows (int) =
2cols (int) =
3target (int) =
9Returns (boolean)
trueExample 2
Input
matrix (int[][]) =
[[1,3,5],[7,9,11]]rows (int) =
2cols (int) =
3target (int) =
4Returns (boolean)
falseExample 3
Input
matrix (int[][]) =
[[1]]rows (int) =
1cols (int) =
1target (int) =
1Returns (boolean)
trueUse binary search by treating the matrix as a flattened sorted array.
The virtual array has rows * cols positions. For any middle index, convert it back to matrix coordinates using row = mid / cols and col = mid % cols.
Compare the middle value with the target and move the search range just like normal binary search.
Pseudocode:
function searchSortedMatrix(matrix, rows, cols, target):
left = 0
right = rows * cols - 1
while left <= right:
mid = (left + right) / 2
row = mid / cols
col = mid % cols
value = matrix[row][col]
if value == target:
return true
else if value < target:
left = mid + 1
else:
right = mid - 1
return falseReady to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run