剑指offer 面试题4:二维数组中的查找【C++版本】

题目总结与代码归档：
【剑指offer-2】题目目录【C++版本】

GitHub代码路径： GitHub

面试题4

二维数组中的查找

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

解题思路

由于每一行都按照从左到右递增，每一列都按照从上到下的递增，右上角的数A必然大于所在行小于所在列，我们可以将需要判断的数X与右上角的数A比较。X > A剔除A所在行；X < A 剔除A所在列，再在剔除后的数组中找右上角数A与X比较
如下图 a b c d，二维数组中查找数字7

代码实现

# include<iostream>

using namespace std;

bool Find(int* matrix, int rows, int columns, int number);

int main()
{
	int matrix[4][4] = { { 1, 2, 8, 9 },{ 2, 4, 9, 12 },{ 4, 7, 10, 13 },{ 6, 8, 11, 15 } };
	// 将二维数组当一维数组操作
	bool ret = Find(*matrix, 4, 4, 7);
	if (ret)
		cout << "found" << endl;
	else
		cout << "not found" << endl;
	system("pause");
	return 0;
}

bool Find(int* matrix, int rows, int columns, int number)
{
	bool found = false;
		
	if (matrix != nullptr&&rows>0&&columns>0)
	{
		// 从右上角开始 也就是 0行 columns - 1 列
		int row = 0;
		int column = columns - 1;
		// 迭代处理 数据范围 逐步向左下角
		while (row < rows && column > 0)
		{
			// 右上角的数
			int test_num = matrix[row * columns + column]; // 当一维数组操作
			// 找到
			if (test_num == number) {
				found = true;
				break;
			}
			// 根据 test_num 与 number 大小关系 ，移动 row column(剔除行或者列)
			else if (test_num < number)	//剔除行
				row++;
			else   //剔除列
				column--;
		}

	}
	return found;
}

参考资料：

---

GitHub链接：
https://github.com/lichangke
CSDN首页：
https://me.csdn.net/leacock1991
欢迎大家来一起交流学习