easyBinary SearchPattern: Binary Search
Sorted Matrix Search Solution
Problem Statement
You are given a 2D sorted matrix and a target number. Implement a function to find the indices of the target number in the matrix.
Examples
Example 1:
Input:[[1, 3, 5], [2, 4, 6], [7, 8, 9]], 5
Output:[[0,2]]
Explanation: The target number 5 is located at row 2 and column 2 in the matrix.
Example 2:
Input:[[-1, 2, 3], [4, 5, 6], [7, 8, 9]], 0
Output:[]
Explanation: The target number 0 is located at row 0 and column 0 in the matrix.
Example 3:
Input:[[1, 3, 5], [2, 4, 6], [7, 8, 9]], 9
Output:[2, 2]
Explanation: The target number 9 is located at row 2 and column 2 in the matrix.
Constraints
- The matrix is sorted in ascending order
- The target number may or may not be present in the matrix
- The matrix contains only unique elements
- The matrix is not empty
- The target number is an integer
Time: O(m + n) Space: O(1)
Use a binary search approach to find the target number in the matrix, taking advantage of the sorted order.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
def sorted_matrix_search(matrix, target): result = [] for i in range(len(matrix)): for j in range(len(matrix[i])): if matrix[i][j] == target: result.append([i, j]) return result