---
title: "Поиск в матрице (отсортированная сетка)"
url: https://algopath.pro/ru/patterns/matrix-search
language: ru
summary: "В сетке, отсортированной в обе стороны, из угла есть только одно направление. Сравнение отбрасывает целый ряд или столбец."
updated: 2026-08-24
---

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

В сетке, отсортированной в обе стороны, из угла есть только одно направление. Сравнение отбрасывает целый ряд или столбец.

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

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

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

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

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

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

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

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

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

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

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

- **Бинарный поиск (массив)** - Если каждый ряд продолжает предыдущий, сетка это один отсортированный список. Тогда работает обычный бинарный поиск.
- **Два указателя (с концов)** - Ход лесенкой это та же идея в двух измерениях. За шаг двигается ровно один индекс.
- **Обход матрицы (спираль / диагонали)** - Там посещается каждая клетка в выбранном порядке. Здесь большинство клеток не читается вовсе.
- **Линейный поиск** - Перебор работает и стоит O(rc). Расточительным его делает как раз наличие порядка.

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

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

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

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

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

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

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

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

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

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

- **Стартуют не из того угла** Левая верхняя клетка меньше обоих соседей и направления не даёт. Начинайте справа сверху или слева снизу.
- **Считают построчную сетку полностью отсортированной** Поиску по позициям нужно, чтобы каждый ряд продолжал предыдущий. Проверьте это до развёртки.
- **Сортируют всю сетку** Так выбрасывается структура, которую вам дали. Плюс это стоит rc log rc.
- **Возвращают среднего кандидата** При поиске по значению ответ обязан существовать в сетке. Сжимайте, пока границы не сойдутся.

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

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

## JavaScript

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

## Python

```python
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
```

## PHP

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