Поиск в матрице (отсортированная сетка)

O(m+n)

Начните с угла матрицы, отсортированной по строкам и столбцам (хорошо подходит верхний правый), и сравнивайте с целью: если больше, отбросьте столбец, если меньше, отбросьте строку. Каждое сравнение отбрасывает целую строку или столбец.

Сигналы

матрица отсортирована и по строкам, и по столбцампоиск значения в 2D отсортированной сеткеначать с угла и отбрасывать строку или столбеци строки, и столбцы монотонны

Шаблон

function searchMatrix(matrix, target) {
    let row = 0;
    let col = matrix[0].length - 1;
    while (row < matrix.length && col >= 0) {
        const v = matrix[row][col];
        if (v === target) return true;
        if (v > target) col--;
        else row++;
    }
    return false;
}

Похоже, но не то

Бинарный поиск (массив): Бинарный поиск делит пополам один отсортированный 1-D массив по индексу. У матрицы, отсортированной по строкам и столбцам, нет единого отсортированного порядка для бинарного поиска, поэтому «лестничный» обход начинается с угла и отбрасывает целую строку или столбец на каждом шаге, находя значение за O(m+n).

сетка до ~1e3 x 1e3, один обход из угла с отбрасыванием строки или столбца на каждом шаге -> O(m+n): существенно меньше O(mn) при переборе всех ячеек.

Изучить этот паттерн