Search 2D Matrix

Write a function to search for a target value in a sorted 2D matrix.

binary search 2d matrix searching

You are given a 2D list `matrix` of integers where each row is sorted in ascending order, and the first integer of each row is greater than the last integer of the previous row (so the entire matrix is in strictly increasing order when read row-major). Write a function `search_matrix(matrix, target)` that returns `True` if `target` is present in the matrix, and `False` otherwise. Your solution must run in O(log(m * n)) time, where m is the number of rows and n is the number of columns. The matrix is guaranteed to have at least one row and one column.

Constraints

- 1 <= len(matrix) <= 100
- 1 <= len(matrix[0]) <= 100
- -10^9 <= matrix[i][j] <= 10^9
- -10^9 <= target <= 10^9
- All rows are sorted non-decreasingly, and the first element of each row is greater than the last element of the previous row.
- Time complexity O(log(m * n)), space O(1).

Example

```python
>>> search_matrix([[1,3,5,7],[10,11,16,20],[23,30,34,60]], 3)
True
>>> search_matrix([[1,3,5,7],[10,11,16,20],[23,30,34,60]], 13)
False
>>> search_matrix([[4]], 4)
True
```

20 points ~25 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think of the matrix as a single sorted list of length m*n.

Use binary search on the flattened index, converting to row and column with integer division and modulo.

Compare the middle element with the target to narrow the search.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.