All problems

Search a 2D Matrix

Medium · binary search

You are given a grid of integers matrix and an integer target. Every row is sorted in ascending order, and the first number of each row is greater than the last number of the row above it. Return True if target is in the grid and False otherwise.

Examples

Example 1

Input: matrix = [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]], target = 3

Output: True

3 is the second number of 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 sit between 11 and 16, and it is not there.

Example 3

Input: matrix = [[1]], target = 1

Output: True

Constraints

• 1 <= m, n <= 100
• -10^4 <= matrix[i][j], target <= 10^4
• Each row is sorted ascending, and matrix[i][0] > matrix[i - 1][n - 1] for every i > 0.