Поиск заданного числа в упорядоченной двумерной матрице

Условие

Требуется реализовать эффективный алгоритм, который ищет число t в целочисленной матрице размером m × n. Матрица обладает двумя свойствами:

• В каждой строке элементы упорядочены по возрастанию слева направо.
• Первый элемент любой строки больше последнего элемента предыдущей строки.

Пример: Вход: mat = [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]], t = 3 Вывод: true

Ответ

Рассматривайте прямоугольную матрицу как один отсортированный массив. Бинарный поиск по плоскому индексу i обращается к mat[i / n][i % n] и работает за O(log(mn)).

bool searchMatrix(const std::vector<std::vector<int>>& mat, int t) {
    if (mat.empty() || mat[0].empty()) return false;
    const std::size_t cols = mat[0].size();
    std::size_t lo = 0, hi = mat.size() * cols;
    while (lo < hi) {
        const auto mid = lo + (hi - lo) / 2;
        const int value = mat[mid / cols][mid % cols];
        if (value == t) return true;
        if (value < t) lo = mid + 1;
        else hi = mid;
    }
    return false;
}

Предполагаются одинаковая длина строк и размер произведения, представимый в std::size_t. Дополнительная память O(1). Если строки отсортированы, но между соседними строками указанного отношения нет, этот алгоритм неприменим.