#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <iomanip>
#include <ctime>
#include <algorithm>
#include <vector>
#include <string>
#include <sstream>
#include <iterator>

bool Compare(std::vector<int>::iterator iterElem, std::vector<int>::iterator end, std::vector<int> target);
unsigned BinSearch(std::vector<int>::iterator left, std::vector<int>::iterator right, int tgt);

int main()
{
	setlocale(LC_ALL, "Rus");
	int n, m;
m1:	for (;;)
	{
		std::cout << "Введите количество строк (от 1 до 15): ";
		if (!(std::cin >> n) || n < 1 || n > 15)
		{
			std::cin.clear();
			std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
			std::cout << "Ошибка" << std::endl;
			continue;
		}
		std::cout << "Введите количество столбцов (от 1 до 15): ";
		if (!(std::cin >> m) || m < 1 || m > 15)
		{
			std::cin.clear();
			std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
			std::cout << "Ошибка" << std::endl;
			continue;
		}
		break;
	}
	srand(time(0));
	std::vector<std::vector<int>> matrix;
	for (auto j = 0; j < m; ++j)
	{
		std::vector<int> buf;
		for (auto i = 0; i < n; ++i)
			buf.push_back(rand() % 201 - 100);
		matrix.push_back(buf);
	}
	std::cout << "\nИзначальный массив:\n" << std::endl;
	for (auto i = 0; i < n; ++i)
	{
		for (const auto& column : matrix)
			printf("%4d ", column[i]);
		std::cout << std::endl;
	}
	std::string line;
	std::vector<int> numbers;
	std::cout << "Введите элемент (последовательность элементов через пробел) для поиска: " << std::endl;
	std::cin.clear();
	std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
	std::getline(std::cin, line);
	std::istringstream stream(line);
	std::copy(std::istream_iterator<int>(stream),
		std::istream_iterator<int>(),
		std::back_inserter(numbers));

	for (auto column = matrix.begin() + 1; column != matrix.end(); ++++column)
		for (auto elem = (*column).begin(); elem != (*column).end(); ++elem)
			if (Compare(elem, (*column).end(), numbers))
				std::cout << "(" << std::distance((*column).begin(), elem) + 1
					<< ", " << std::distance(matrix.begin(), column) + 1 << ')' << std::endl;

	int target;
	for (;;)
	{
		std::cout << "Введите элемент для бинарного поиска: " << std::endl;
		if (!(std::cin >> target))
		{
			std::cin.clear();
			std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
			std::cout << "Ошибка" << std::endl;
			continue;
		}
		break;
	}
	unsigned idx = 1;
	for (auto column : matrix)
	{
		std::sort(column.begin(), column.end());
		std::cout << "Найдено в " << idx++ << " столбце: "
			<< BinSearch(column.begin(), column.end() - 1, target) << std::endl;
	}
	system("pause");
	return 0;
}

bool Compare(std::vector<int>::iterator iterElem, std::vector<int>::iterator end, std::vector<int> target)
{
	if (std::distance(iterElem, end) < std::distance(target.begin(), target.end()))
		return false;
	for (auto iterTarget = target.begin();
		iterElem != end && iterTarget != target.end();
		++iterElem, ++iterTarget)
	{
		if (*iterElem != *iterTarget)
			return false;
	}
	return true;
}

unsigned BinSearch(std::vector<int>::iterator left, std::vector<int>::iterator right, int tgt)
{
	if (left > right)
		return 0;
	const auto avg = left + (right - left) / 2;
	if (tgt < *avg)
		return BinSearch(left, avg - 1, tgt);
	else if (tgt > *avg)
		return BinSearch(avg + 1, right, tgt);
	else
	{
		unsigned count = 1;
		if (avg != right)
			for (auto tmp = avg + 1; tmp != right && *tmp++ == tgt; count++);
		if (avg != left)
			for (auto tmp = avg - 1; tmp != left && *tmp-- == tgt; count++);
		return count;
	}
}