Search a 2D Matrix

Easy

You are given an m x n integer matrix with the following properties:

Each row is sorted in ascending order from left to right.
The first integer of each row is greater than the last integer of the previous row.

Given an integer target, return true if target exists in the matrix. Otherwise, return false.

You must solve the problem in O(log(m × n)) time.

Example 1

Input

m = 3
n = 4
matrix =
1 3 5 7
10 11 16 20
23 30 34 60
target = 3

Output

true

Explanation

The value 3 exists in the matrix at row 0, column 1.

Example 2

Input

m = 3
n = 4
matrix =
1 3 5 7
10 11 16 20
23 30 34 60
target = 13

Output

false

Explanation

13 does not appear anywhere in the matrix.

Constraints

1 <= m

n <= 100

-10^4 <= matrix[i][j] <= 10^4

All integers in each row are sorted in ascending order.

The first integer of each row is greater than the last integer of the previous row.

-10^4 <= target <= 10^4

Hints:

Hint 1

The entire matrix can be viewed as one sorted 1D array.

Hint 2

Use binary search on the range:

0 to (m × n) - 1

For a flattened index mid:

row = mid / n col = mid % n

Author & Technical Reviewer

Technically reviewed by: ExamAdda Technical Review Team

Technical Reviewers, ExamAdda

Software engineers at ExamAdda who check every article's definitions, complexity claims and code examples before and after publishing.

Published

Aug 22, 2026

Last updated

Aug 22, 2026

Content Verification Methodology

Definitions and complexity claims were checked against authoritative computer-science references. Code examples were compiled and tested with standard, boundary and edge-case inputs.

Report a correction:editorial@examadda.org

Auto

Loading editor...

Input

Expected Output