74. Поиск в 2D-матрице (Search a 2D Matrix)

Задание.

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

• Каждая строка отсортирована по возрастанию.

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

Получена матрица matrix и целочисленное target.

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

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

Пример 1.

Входные данные: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3

Результат: true

Пример 2.

Входные данные: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13

Результат: false

Решение.

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int row = matrix.size();
        int col = matrix[0].size();
        int low = 0;
        int high = row*col -1;
        int mid;
        int cell;
        while(low <= high) {
            mid = low + (high-low)/2;
            if((cell = matrix[mid/col][mid%col]) == target) return true;
            else if(cell < target) low = mid+1;
            else high = mid - 1;
        }
        return false;
    }
};

Способ решения.