/*
* 在一个二维数组中，每一行都是按照从左到右
* 递增的顺序排序，每一列都是按照从上到下递增
* 的顺序排序。请完成一个函数，输入这样的一个
二位数组和一个整数，判断数组中是否含有该整数。
*/

/*
* 解法1：暴力搜索法，时间复杂度为O(n^2)
*/

#include<iostream>

using namespace std;

bool search_num(const int* nums,int rows, int cols, const int& num)
{
	if (nums != nullptr && rows > 0 && cols > 0)
	{
		for (int i = 0; i < rows; i++)
		{
			for (int j = 0; j < cols; j++)
			{
				if (nums[i * cols + j] == num)
				{
					return true;
				}
			}
		}
	}

	return false;
}

int main()
{
	const int rows = 4;
	const int cols = 4;
	const int lens = rows * cols;
	int* nums = new int[lens]();
	for (int i = 0; i < lens; ++i)
	{
		nums[i] = i + 1;
	}

	int num;           //要查找的数字
	cin >> num;

	bool result = search_num(nums, rows, cols, num);

	if (result)
	{
		cout << "the matrix has this number." << endl;
	}
	else
	{
		cout << "the matrix do not has this number." << endl;
	}
　　　　　
　　　　　delete[] nums;
　　　　  nums = nullptr;
	
}

/*
*解法2：利用搜索数组的特性，首先选取数组中右上角的数字。如果该数字等于要查找的数字，则
* 查找结束；如果该数字大于要查找的数字，则剔除这个数字所在的列；如果这个数字小于要查找
的数字，则剔除这个数字所在的行。这样就可以一步一步的缩小范围了。* 
*/

#include<iostream>

using namespace std;

bool Find(const int* matrix, int rows, int cols, const int& num)
{
	if (matrix != nullptr && rows > 0 && cols > 0)
	{
		int row = 0;
		int col = cols - 1;
		while (row < rows && col >= 0)
		{
			if (matrix[row * cols + col] == num)
			{
				return true;
			}
			else if (matrix[row * cols + col] > num)
			{
				col--;
			}
			else
			{
				row++;
			}
		}
	}

	return false;
}

int main()
{
	const int rows = 4;
	const int cols = 4;
	const int lens = rows * cols;
	int* nums = new int[lens]();
	for (int i = 0; i < lens; ++i)
	{
		nums[i] = i + 1;
	}

	int num;           //要查找的数字
	cin >> num;

	bool result = Find(nums, rows, cols, num);

	if (result)
	{
		cout << "the matrix has this number." << endl;
	}
	else
	{
		cout << "the matrix do not has this number." << endl;
	}

　　　　　delete[] nums;
　　　　  nums = nullptr;

}