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

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

Отсортированные сетки бывают двух видов. В одной каждый ряд продолжает предыдущий, в другой ряды и столбцы просто возрастают.

Первый вид это отсортированный список, свёрнутый в ряды. Бинарный поиск идёт по r умножить на c позициям.

Для второго вида начните с правого верхнего угла. Слева от него всё меньше, а снизу всё больше.

Если значение там слишком велико, идите влево. Это сразу отбрасывает целый столбец.

Если оно слишком мало, идите вниз. Это отбрасывает целый ряд.

Каждый шаг убирает один ряд или один столбец. Поэтому обход кончается за r плюс c шагов.

1. старт на 7, правый верхИщем 5 в сетке, возрастающей в обе стороны.
2. 7 слишком великаВсё ниже семёрки в этом столбце больше. Идём влево.
3. 4 слишком малаВсё левее четвёрки в этом ряду меньше. Идём вниз.
4. теперь на 5Значение под обходом совпало с искомым.
5. три шагаДевять клеток, три сравнения. Две линии отброшены целиком.

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;
}

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

K-е наименьшее значение в отсортированной сетке

В сетке возрастают и ряды, и столбцы. Верните её k-е наименьшее значение.

Развернуть и отсортировать можно, но это читает каждую клетку.

Ведите бинарный поиск по диапазону значений, а не по позициям.

Для кандидата посчитайте, сколько клеток не больше него. Это число и говорит, какую половину оставить.

function kthSmallest(matrix, k) {
    const n = matrix.length;
    let lo = matrix[0][0];
    let hi = matrix[n - 1][n - 1];

    const countNotAbove = (value) => {
        let count = 0;
        let row = n - 1;

        // one staircase walk, starting from the bottom-left corner
        for (let col = 0; col < n; col++) {
            while (row >= 0 && matrix[row][col] > value) row--;
            count += row + 1;
        }

        return count;
    };

    while (lo < hi) {
        const mid = lo + Math.floor((hi - lo) / 2);
        if (countNotAbove(mid) >= k) hi = mid;
        else lo = mid + 1;
    }

    return lo;
}

Поиск в матрице (отсортированная сетка): когда применять?

Эти формулировки в условии ведут сюда:

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

Поиск в матрице (отсортированная сетка): с чем путают?

• Бинарный поиск (массив) (Binary search (array)): Если каждый ряд продолжает предыдущий, сетка это один отсортированный список. Тогда работает обычный бинарный поиск.
• Два указателя (с концов) (Two pointers (opposite ends)): Ход лесенкой это та же идея в двух измерениях. За шаг двигается ровно один индекс.
• Обход матрицы (спираль / диагонали) (Matrix traversal (spiral / diagonal)): Там посещается каждая клетка в выбранном порядке. Здесь большинство клеток не читается вовсе.
• Линейный поиск (Linear search): Перебор работает и стоит O(rc). Расточительным его делает как раз наличие порядка.

Поиск в матрице (отсортированная сетка): частые ошибки

• Стартуют не из того угла

  Левая верхняя клетка меньше обоих соседей и направления не даёт. Начинайте справа сверху или слева снизу.

• Считают построчную сетку полностью отсортированной

  Поиску по позициям нужно, чтобы каждый ряд продолжал предыдущий. Проверьте это до развёртки.

• Сортируют всю сетку

  Так выбрасывается структура, которую вам дали. Плюс это стоит rc log rc.

• Возвращают среднего кандидата

  При поиске по значению ответ обязан существовать в сетке. Сжимайте, пока границы не сойдутся.

Поиск в матрице (отсортированная сетка): задачи с собеседований

• Поиск в двумерной матрице: Один отсортированный список, свёрнутый в ряды.
• Поиск в двумерной матрице II: Ход лесенкой из угла.
• K-е наименьшее в отсортированной матрице: Бинарный поиск по значениям с подсчётом на кандидата.
• Поиск пика в матрице: Бинарный поиск по столбцам.
• Число отрицательных в отсортированной матрице: Та же лесенка, но со счётом вместо совпадения.
• Медиана построчно отсортированной матрицы: Считайте, сколько клеток не больше кандидата.
• Наименьший общий элемент всех рядов: По указателю на ряд, двигаются вместе.

Поиск в матрице (отсортированная сетка): сложность по времени и памяти

O(m+n)

Сетка r на c даёт O(r + c) при ходе лесенкой. Полностью отсортированная сетка позволяет O(log rc).