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

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

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

Первый вид это отсортированный список, свёрнутый в ряды. Бинарный поиск идёт по 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;
}

function searchMatrix(matrix: number[][], target: number): boolean {
    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;
}

def search_matrix(matrix, target):
    row, col = 0, len(matrix[0]) - 1
    while row < len(matrix) and col >= 0:
        v = matrix[row][col]
        if v == target:
            return True
        if v > target:
            col -= 1
        else:
            row += 1
    return False

function searchMatrix(array $matrix, int $target): bool {
    $row = 0;
    $col = count($matrix[0]) - 1;
    while ($row < count($matrix) && $col >= 0) {
        $v = $matrix[$row][$col];
        if ($v === $target) return true;
        if ($v > $target) $col--;
        else $row++;
    }
    return false;
}

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

    public static bool SearchMatrix(int[][] matrix, int target) {
        int row = 0;
        int col = matrix[0].Length - 1;
        while (row < matrix.Length && col >= 0) {
            int 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 отсортированной сетке» или «начать с угла и отбрасывать строку или столбец». Решение на нём обычно укладывается в O(m+n).

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

Слова в условии для всех паттернов собраны в одной таблице: шпаргалка по паттернам алгоритмов.

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

Паттерн «Поиск в матрице (отсортированная сетка)» чаще всего путают с этими паттернами: Бинарный поиск (массив), Два указателя (с концов), Обход матрицы (спираль / диагонали) и Линейный поиск.

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

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

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

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

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

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

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

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

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

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

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

Паттерн «Поиск в матрице (отсортированная сетка)» решает такие задачи с собеседований: Поиск в двумерной матрице, Поиск в двумерной матрице II, K-е наименьшее в отсортированной матрице, Поиск пика в матрице, Число отрицательных в отсортированной матрице, Медиана построчно отсортированной матрицы и Наименьший общий элемент всех рядов.

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

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

У паттерна «Поиск в матрице (отсортированная сетка)» целевая сложность O(m+n).

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