Practice › Binary Search
Search a 2D Matrix
Medium · Binary Search · Asked at Amazon, Microsoft, Meta, Bloomberg
Each row of the matrix is sorted, and the first value of every row is greater than the last value of the previous row. Print YES if target is in the matrix, otherwise NO.
Input
First line: n m target. Next n lines: m integers each.
Output
YES or NO.
Constraints
- 1 ≤ n, m ≤ 1000
- -10^9 ≤ values ≤ 10^9
Read as one sorted array of length n·m: index i is at row i / m, column i % m. One binary search.
Example 1
Input
3 4 3 1 3 5 7 10 11 16 20 23 30 34 60
Output
YES
Example 2
Input
3 4 13 1 3 5 7 10 11 16 20 23 30 34 60
Output
NO
Hints
- Reading the rows one after another gives a single sorted list of n·m numbers.
- Binary search on index i in [0, n·m − 1]; the element is g[i / m][i % m].
Approach
Because each row starts after the previous one ends, the matrix is a sorted array laid out row by row. Run a normal binary search over virtual indices and convert each index to (row, column) with division and modulo.
Complexity: O(log(n·m)) time · O(1) extra space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m;
long long t;
cin >> n >> m >> t;
vector<vector<long long>> g(n, vector<long long>(m));
for (auto &row : g)
for (auto &x : row) cin >> x;
long long lo = 0, hi = (long long)n * m - 1;
while (lo <= hi) {
long long mid = (lo + hi) / 2;
long long v = g[mid / m][mid % m];
if (v == t) {
cout << "YES\n";
return 0;
}
if (v < t) lo = mid + 1;
else hi = mid - 1;
}
cout << "NO\n";
return 0;
}Python solution
import sys
data = list(map(int, sys.stdin.read().split()))
n, m, t = data[0], data[1], data[2]
g = data[3:]
lo, hi, found = 0, n * m - 1, False
while lo <= hi:
mid = (lo + hi) // 2
v = g[(mid // m) * m + mid % m]
if v == t:
found = True
break
if v < t:
lo = mid + 1
else:
hi = mid - 1
print("YES" if found else "NO")Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), m = sc.nextInt();
long t = sc.nextLong();
long[][] g = new long[n][m];
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) g[i][j] = sc.nextLong();
long lo = 0, hi = (long) n * m - 1;
while (lo <= hi) {
long mid = (lo + hi) / 2;
long v = g[(int) (mid / m)][(int) (mid % m)];
if (v == t) {
System.out.println("YES");
return;
}
if (v < t) lo = mid + 1;
else hi = mid - 1;
}
System.out.println("NO");
}
}