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

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

Каждая строка отсортирована в порядке неубывания.
Первое число каждой строки больше последнего числа предыдущей строки.
Дано целое число target. Верните true, если target присутствует в матрице, и false в противном случае.

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

Пример:

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

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

1⃣Инициализируйте индексы слева и справа: left = 0 и right = m x n - 1.

2⃣Пока left <= right:
Выберите индекс посередине виртуального массива в качестве опорного индекса: pivot_idx = (left + right) / 2.

3⃣Индекс соответствует row = pivot_idx // n и col = pivot_idx % n в исходной матрице, и, следовательно, можно получить pivot_element. Этот элемент делит виртуальный массив на две части.
Сравните pivot_element и target, чтобы определить, в какой части нужно искать target.

😎 Решение:

function searchMatrix($matrix, $target) {
    $m = count($matrix);
    if ($m == 0) return false;
    $n = count($matrix[0]);
    $left = 0;
    $right = $m * $n - 1;

    while ($left <= $right) {
        $pivotIdx = intdiv($left + $right, 2);
        $pivotElement = $matrix[intdiv($pivotIdx, $n)][$pivotIdx % $n];
        if ($target == $pivotElement) {
            return true;
        } else {
            if ($target < $pivotElement) {
                $right = $pivotIdx - 1;
            } else {
                $left = $pivotIdx + 1;
            }
        }
    }
    return false;
}

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