codejump
MediumPro challengePythonJavaScriptTypeScript

Binary Search — Search a 2D Matrix

AlgorithmsBinary SearchMatrix

solve(matrix, target) — every row of matrix is sorted ascending, and the first
value of each row is greater than the last value of the previous row. Return true
when target is in the matrix. Run in O(log(rows × cols)).

Read the matrix as one flat sorted array of rows × cols cells without building it:
the flat index i lives at row floor(i / cols), column i % cols.

Examples

solve([[1,3,5,7],[10,11,16,20],[23,30,34,60]], 3)   → true
solve([[1,3,5,7],[10,11,16,20],[23,30,34,60]], 13)  → false
solve([[1]], 1)                                      → true

Sample tests

Test #1Present in the first row
Input: [[[1,3,5,7],[10,11,16,20],[23,30,34,60]],3]
Output: true
Test #2Absent between rows
Input: [[[1,3,5,7],[10,11,16,20],[23,30,34,60]],13]
Output: false
Test #3Single cell, present
Input: [[[1]],1]
Output: true
← All challenges