Задача: 240. Search a 2D Matrix II
Сложность: medium

Напишите эффективный алгоритм, который ищет значение target в матрице целых чисел размером m на n. У этой матрицы есть следующие свойства:

Целые числа в каждой строке отсортированы по возрастанию слева направо.
Целые числа в каждом столбце отсортированы по возрастанию сверху вниз.

Пример:

Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
Output: true

👨‍💻 Алгоритм:

1⃣Проверка матрицы: Перед началом поиска убедитесь, что матрица не пуста и не содержит null.

2⃣Итерация по диагоналям: Итерируйте по диагоналям матрицы, используя инвариант отсортированности срезов строк и столбцов, начиная с текущей позиции (строка, столбец). Для каждого такого среза используйте бинарный поиск для нахождения целевого значения.

3⃣Бинарный поиск и завершение: Продолжайте бинарный поиск до тех пор, пока не исчерпаете все диагонали (в этом случае возвращается False) или пока не найдете целевое значение (в этом случае возвращается True). Функция бинарного поиска должна уметь работать как с рядами, так и с колонками матрицы.

😎 Решение:

class Solution {
    private func binarySearch(_ matrix: [[Int]], _ target: Int, _ start: Int, _ vertical: Bool) -> Bool {
        var lo = start
        var hi = vertical ? matrix[0].count - 1 : matrix.count - 1

        while hi >= lo {
            let mid = (lo + hi) / 2
            if vertical {
                if matrix[start][mid] < target {
                    lo = mid + 1
                } else if matrix[start][mid] > target {
                    hi = mid - 1
                } else {
                    return true
                }
            } else {
                if matrix[mid][start] < target {
                    lo = mid + 1
                } else if matrix[mid][start] > target {
                    hi = mid - 1
                } else {
                    return true
                }
            }
        }
        return false
    }

    func searchMatrix(_ matrix: [[Int]], _ target: Int) -> Bool {
        if matrix.isEmpty || matrix[0].isEmpty {
            return false
        }

        let shorterDim = min(matrix.count, matrix[0].count)
        for i in 0..<shorterDim {
            if binarySearch(matrix, target, i, true) || binarySearch(matrix, target, i, false) {
                return true
            }
        }
        return false
    }
}

Ставь 👍 и забирай 📚 Базу знаний