Modified Binary Search
LC #74Medium
Search a 2D Matrix
Modified Binary Search
AmazonGoogleMicrosoftAppleProblem
Search for a target in an m×n matrix where each row is sorted and the first integer of each row > last integer of previous row.
arraybinary-searchmatrix
Constraints
- ›m == matrix.length
- ›n == matrix[i].length
- ›1 ≤ m, n ≤ 100
- ›-10⁴ ≤ matrix[i][j] ≤ 10⁴
- ›Each row sorted; first element of each row > last of previous
Example
Input
matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3Output
trueWhy
Treat matrix as flattened sorted array. Binary search on virtual index.