Поиск в Отсортированной МатрицеSaddleback Search

Поиск начинается в правом верхнем углу матрицы — единственной клетке, про которую сразу известно и то, что она максимальна в своей строке, и то, что она минимальна в своём столбце. Пусть текущая клетка (r, c) содержит значение v. Если v == x — готово. Если v > x, то x не может находиться нигде в столбце c (все элементы столбца ниже (r,c) ещё больше, так как столбец отсортирован по возрастанию вниз) — столбец c целиком отбрасывается сдвигом c влево. Если v < x, аналогично отбрасывается строка r сдвигом r вниз (все элементы левее в этой строке ещё меньше). Инвариант — то, что "если x есть в матрице, он лежит в оставшемся прямоугольнике [0..rows) × [0..c]" — сохраняется на каждом шаге, а сам указатель либо движется влево, либо вниз, то есть суммарно делает не больше rows + cols шагов.The search starts at the matrix's top-right corner — the one cell known immediately to be both the maximum in its row and the minimum in its column. Let the current cell (r, c) hold value v. If v == x, done. If v > x, x can't be anywhere in column c (every element below (r,c) in that column is even larger, since the column is sorted ascending downward) — the whole column c is discarded by moving c left. If v < x, symmetrically row r is discarded by moving r down (every element to the left in that row is even smaller). The invariant — "if x is in the matrix, it lies in the remaining rectangle [0..rows) × [0..c]" — is preserved at every step, and the pointer itself either moves left or down, so it takes at most rows + cols steps total.

std::optional<std::pair<int,int>> saddleback_search(
    const std::vector<std::vector<int>>& m, int x) {
    if (m.empty() || m[0].empty()) return std::nullopt;
    int r = 0, c = (int)m[0].size() - 1;  // правый верхний угол// top-right corner
    while (r < (int)m.size() && c >= 0) {
        if (m[r][c] == x) return std::make_pair(r, c);
        else if (m[r][c] > x) --c;   // отбросить столбец// discard the column
        else ++r;                   // отбросить строку// discard the row
    }
    return std::nullopt;
}

Жёлтая клетка — текущая позиция указателя. Затемнённые клетки — уже отброшенные строки/столбцы. Указатель всегда стартует в правом верхнем углу и движется только влево или вниз.The yellow cell is the pointer's current position. Dimmed cells are already-discarded rows/columns. The pointer always starts at the top-right corner and moves only left or down.

Заманчиво ожидать логарифмическую сложность по аналогии с 1D бинарным поиском, но у двумерной отсортированности гораздо более слабая структура: в отличие от одномерного массива, где сравнение с одним элементом делит весь оставшийся набор кандидатов пополам, сравнение с одной клеткой матрицы устраняет только одну строку или один столбец — то есть O(n) или O(m) кандидатов из O(n·m), а не половину. Можно показать (через явные примеры "тяжёлых" матриц), что Ω(n+m) сравнений необходимы в худшем случае для любого алгоритма, работающего только через сравнение элементов — O(n+m) этого алгоритма, следовательно, асимптотически оптимально, не будучи логарифмическим.It's tempting to expect logarithmic complexity by analogy with 1D binary search, but two-dimensional sortedness has a much weaker structure: unlike a 1D array, where comparing against one element halves the entire remaining candidate set, comparing against one matrix cell eliminates only one row or one column — that is, O(n) or O(m) candidates out of O(n·m), not half. It can be shown (via explicit "hard" matrix examples) that Ω(n+m) comparisons are necessary in the worst case for any algorithm working only through element comparison — this algorithm's O(n+m) is therefore asymptotically optimal, without being logarithmic.