Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. Reading the rows one after another gives a single sorted list of n·m numbers.
  2. 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");
    }
}

Solve Search a 2D Matrix online · All practice problems