一、题目

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

二、算法分析

一个从左到右，从上到下递增的二维数组，我们可以从数组的左下角或者右上角开始遍历，这样当我们将numbert与遍历的元素做比较后（以右上角为例），如果比number大，剔除所在的列，如果比number小，则剔除所在的行，否则，找到了要查找的数字，查找结束

三、代码实现

#include<stdio.h>
#include<stdlib.h>
bool Find(int *matrix,int rows,int columns,int number)
{
	bool found=false;  //初始化为false

	if(matrix!=nullptr&&rows>0&&columns>0)
	{
		//右上角坐标
		int row=0;
		int column=columns-1;
		//遍历比较
		while(row<rows&&columns>=0)
		{
			if(matrix[row*columns+column]==number)
			{
				found=true;  //找到数值
				break;
			}
			else if(matrix[row*columns+column]>number)
				--column;   //剔除列
			else
				++row;      //剔除行
		}
	}
	return found;
}

四、测试及结果

4.1 测试代码

int main()
{
int matrix[4][4]={{1,2,8,9},{2,4,8,12},{4,7,10,13},{6,8,11,16}};
bool f=Find(*matrix,4,4,7);
if(ftrue)
{
printf(“true\n”);
}
if(ffalse)
{
printf(“false\n”);
}
return 0;
}

4.2 测试结果