74. Search a 2D Matrix

Задача

Вам дана целочисленная матрица matrix размера m x n , обладающая следующими двумя свойствами:

• Каждая строка отсортирована в порядке неубывания.
• Первое целое число каждой строки больше последнего целого числа предыдущей строки.

Дано целое число target . Верните true , еслиtargetнаходится в matrix , илиfalseв противном случае.

Вы должны написать решение с временной сложностью O(log(m * n)) .

Примеры

Пример 1

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true

Пример 2

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false

Решение

Решение

/**
 * Временная сложность: O(log(m * n))
 * - Мы рассматриваем матрицу как один отсортированный массив длиной m*n.
 * - Бинарный поиск делит область поиска пополам на каждом шаге.
 * 
 * Пространственная сложность: O(1)
 * - Мы используем только несколько переменных для хранения индексов.
 * - Дополнительная память не зависит от размера входных данных.
 */
var searchMatrix = function(matrix, target) {
    if (!matrix.length || !matrix[0].length) return false;
 
    const rows = matrix.length;
    const cols = matrix[0].length;
 
    // Представляем матрицу как одномерный массив длиной m * n
    let left = 0;
    let right = rows * cols - 1;
 
    while (left <= right) {
        // Находим середину виртуального массива
        const mid = Math.floor((left + right) / 2);
 
        // Преобразуем индекс mid обратно в координаты матрицы [row][col]
        // Важно: делим на количество СТОЛБЦОВ (длину строки)
        const row = Math.floor(mid / cols);
        const col = mid % cols;
 
        const value = matrix[row][col];
 
        if (value === target) {
            return true;
        } else if (value < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
 
    return false;
};