一、题目
在一个二维数组中,每一行都按照从左到右递增的顺序排序。每一列都按照从上到下递增的顺序排序,请完成一个函数,输入这样的一个二维数组和一个整数,判断数组是否含有该整数。
二、算法分析
一个从左到右,从上到下递增的二维数组,我们可以从数组的左下角或者右上角开始遍历,这样当我们将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;
}