Search a 2D Matrix
Part of Practice: Search Templates
You are given an m x n grid of integers with two ordering guarantees: every row is sorted left to right, and the first number of each row is larger than the last number of the row above it. Given a target, return true if it appears anywhere in the grid and false otherwise.
Your solution must run in O(log(m * n)) time — one binary search over the whole grid, not one per row.
The grid has at least one row and one column, and can be up to 100 x 100.
Examples
- Input:
- matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
- Output:
- true
3 appears in the first row.
- Input:
- matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
- Output:
- false
13 falls between 11 and 16 in reading order but is not present.
Hints
One at a time — struggle first, peek second.
Your thinking space — verify on LeetCode, then mark it.