Найти элемент в отсортированной матрице

task70.cpp

#include <algorithm>
#include <cassert>
#include <iostream>
#include <memory>

template <typename T>
class Matrix
{
public:
	Matrix(size_t rows, size_t cols, T value)
		: m_rows(rows)
		, m_cols(cols)
		, m_data(new T[rows * cols])
	{
		for (size_t row = 0; row < rows; ++row)
			for (size_t col = 0; col < cols; ++col)
				*(m_data.get() + row * cols + col) = value;
	}

	Matrix(std::initializer_list<std::initializer_list<T>> args)
	{
		m_rows = args.size();
		m_cols = args.begin()->size();

		m_data.reset(new T[m_rows * m_cols]);

		auto inner = args.begin();
		for (size_t row = 0; row < m_rows; ++row, ++inner)
			std::copy(std::begin(*inner), std::end(*inner), m_data.get() + row * m_cols);
	}

	T operator()(size_t row, size_t col) const
	{
		if (row < 0 || row >= m_rows)
			throw std::invalid_argument("invalid row index");
		if (col < 0 || col >= m_cols)
			throw std::invalid_argument("invalid column index");
		return *(m_data.get() + row * m_cols + col);
	}

	T& operator()(size_t row, size_t col)
	{
		if (row < 0 || row >= m_rows)
			throw std::invalid_argument("invalid row index");
		if (col < 0 || col >= m_cols)
			throw std::invalid_argument("invalid column index");
		return *(m_data.get() + row * m_cols + col);
	}

	size_t rows() const { return m_rows; }
	size_t cols() const { return m_cols; }

	template <typename U>
	friend std::ostream& operator<<(std::ostream& os, const Matrix<U>& matrix);

private:
	std::unique_ptr<T> m_data = nullptr;
	size_t m_rows = 0;
	size_t m_cols = 0;
};

template <typename T>
inline std::ostream& operator<<(std::ostream& os, const Matrix<T>& matrix)
{
	for (size_t row = 0; row < matrix.m_rows; ++row)
	{
		for (size_t col = 0; col < matrix.m_cols; ++col)
			os << *(matrix.m_data.get() + row * matrix.m_cols + col) << ' ';
		os << '\n';
	}
	return os;
}

std::pair<int, int> Task70(const Matrix<int>& matrix, int value)
{
	int row = 0;
	int col = static_cast<int>(matrix.cols() - 1);

	while (col >= 0 && row < matrix.rows())
	{
		const auto current = matrix(row, col);
		if (current == value)
			return std::make_pair(row, col);
		else if (current > value)
			--col;
		else
			++row;
	}
	return std::make_pair(-1, -1);	
}


int main()
{
	Matrix<int> matrix({
		{ 1,  5, 10, 20},
		{ 7,  9, 15, 28},
		{12, 25, 30, 36},
		{22, 35, 45, 50}
	});

	auto answer = Task70(matrix, 45);
	assert(answer.first == 3 && answer.second == 2);
	
	answer = Task70(matrix, 44);
	assert(answer.first == -1 && answer.second == -1);

	system("pause");
	return 0;
}

task70.txt

Задача 70:
Найти элемент в отсортированной матрице (матрица, в которой строки и столбцы отсортированы).
Если такого элемента нет, вывести сообщение об ошибке.

Ход решения:
Начнем с верхнего правого угла матрицы и будем двигаться по элементам, используя следующую логику:
1. Если элемент, на котором мы стоим, равен искомому элементу, возвращаем индексы строки и столбца;
2. Если элемент больше заданного, нам нужно идти в сторону уменьшения - то есть налево по строке;
3. Если элемент меньше заданного, нам нужно идти в сторону увеличения - то есть вниз по столбцу.
Пункты 2-3 справедливы вследствие сортированности строк и столбцов матрицы.
Если при поиске мы вылетели за границы матрицы, значит, матрица не содержит данного элемента.

Сложность алгоритма в худшем случае: O(n+m), где n,m - размерности матрицы.

PS. В ходе решения задачи был написан собственный класс матрицы, реализующий исключительно ту функциональность, которая нужна в рамках этой задачи. Как говорится, любой программист должен, прежде всего, написать свои классы вектора и матрицы. =)