Search a 2D Matrix
Medium· index mapping
Problem
Each row of a matrix is sorted ascending, and the first value of each row is larger than the last value of the previous row. Decide whether a target value is present, in logarithmic time.
Examples
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false
Constraints
- • 1 <= m, n <= 100
- • -10^4 <= matrix[i][j], target <= 10^4
Hints & approach
Hint 1
Read row by row, the whole matrix is one sorted list.
Hint 2
Binary search over indices 0 … m·n - 1.
Hint 3
Index k maps to row k / n and column k % n.
Approachtry the hints first
Because the rows chain together in sorted order, treat the matrix as a virtual sorted array of length m·n. Run a standard binary search over that range, converting each midpoint k to matrix[k / n][k % n]. Return true on a match and false once the search range is empty.
Time O(log(m·n)) · Space O(1)