Search a 2D Matrix
You are given a grid of integers with two properties: every row is sorted in non-decreasing order, and the first value of each row is greater than the last value of the previous row. Return true if target appears in the grid, otherwise false.
Aim for a running time of O(log(m * n)), where the grid has m rows and n columns.
Constraints
1 <= m, n <= 100-10^4 <= matrix[i][j], target <= 10^4
Examples
Example 1
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3 Output: true
3 sits in the first row.
Example 2
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13 Output: false
13 would fall between 11 and 16 in the second row, but it is not there.
Example 3
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 60 Output: true
The last cell is a valid target; treating the grid as one sorted list of 12 values makes this a normal binary search.
JavaScript you'll use: Arrays: create, read, update Numbers, Math and integer tricks
/**
* @param {number[][]} matrix
* @param {number} target
* @return {boolean}
*/
function searchMatrix(matrix, target) {
}
Ctrl/⌘ + ' runs the examples, Ctrl/⌘ + Enter submits. Use console.log freely: output shows under Console. In the editor, press Esc then Tab to move focus out.