天天看点

杨氏矩阵的快速查找方法(超级详细)

介绍

杨氏矩阵是一个不论是横向或者是纵向都是一个

数值不断增大的元素,为了让你们看到更清楚我

给你们特地准备了两份例子(大家不要介意我画的丑)

例子1:

杨氏矩阵的快速查找方法(超级详细)

例子2:

杨氏矩阵的快速查找方法(超级详细)

但是因为画图板可以更好的解释,咱们就用第一个举例子。

如果是一个矩阵去查询一个数字是否在这个矩阵里,那么大多数人的选择应该是一个一个去筛查,代码如下

杨氏矩阵的快速查找方法(超级详细)

这个查找的方法是非常的简单只需要一个一个查找,如果是1000个,1000000个数字那岂不是还要循环好多好多遍,所以如果代码这么写就有点挫了吧,咱们可是有远大抱负的青年,怎么会仅仅满足这个代码,接下来我将给大家讲解如何更快的判断查找的元素在不在这个矩阵里面。

正文

前面说了

杨氏矩阵是一个横纵都是在递增的矩阵,这样咱们就可以找到一个规律,接下来由我给大家画出来:

杨氏矩阵的快速查找方法(超级详细)

大家可以看到我给这个矩阵画了两个框框

什么意思呢???

大家请看这个蓝色框框里面的值,都是不断地变大的

再看看这个紫色的(不太清楚)也是不断地递增

这个呢就是杨氏矩阵的规律,那么有的人可能就会问

啊?这个不就是递增嘛,这个规律跟加快数字的查找有什么关系啊???

接下来我再画个图给大家介绍一下这两个框框的意思

杨氏矩阵的快速查找方法(超级详细)

大家可以看到这个5是这个行最大的一个数,所以说

如果我们要查找的数比5大,那就说明在第1行找不到和我要查找的值一样的数了(因为已经比这一行所有的数都要大了)所以呢我们就可以换到第2行再去判断

杨氏矩阵的快速查找方法(超级详细)

如此往复如果我们要查找的值比这一行最后一个元素还要大那么我们就可以换到下一行,这里关于行的判定解释完了,接下来到了列的判断:

杨氏矩阵的快速查找方法(超级详细)

大家可以看到这个深紫色的圆环依旧是圈在了最右上角的元素上面,大家是不是还可以发现:

杨氏矩阵的快速查找方法(超级详细)

大家可以看到这个右上角的5是绿色圈圈里面最小的一个数,所以大家也应该猜到了,当要查找的元素比5小时,那么就可以去第三列查找了,因为第四最小的数都比我要查找的数大所以我们就可以(4-1=3)去查找第三列

如果我们设置的是N这么大的矩阵那么他的长宽都是N:

杨氏矩阵的快速查找方法(超级详细)

这样以来右上角的元素就为(0,N-1)了,因为长度是5,所以从0开始我的最大值就是(N-1),如此往复

如果我们要查找3,那么我们就可以先进行判断

杨氏矩阵的快速查找方法(超级详细)

咱们用黑色将3圈了出来,由于3比5小,也就是3比右上角的数要小所以我们就(Y-1)这下我们的Y就指向了绿字3所对应的列;

杨氏矩阵的快速查找方法(超级详细)

就这样第4列被咱们删除掉,现在右上角的数为4,但是4依旧比3大于是我们继续(Y-1),这样我们的纵坐标就指向了3;

杨氏矩阵的快速查找方法(超级详细)

查找到了3,当然查找别的值也是如此往复是不是比之前的一个一个查找块很多一次性就可以排除一行或者列,

当然左下角也是可以的,但是左上角和右下角就不建议;好的接下来代码实现,为了更直观的观看我将用函数来进行处理(初始化函数):

int main()
{
	printf("请输入矩阵的大小\n");
	int n = 0;
	scanf("%d", &n);
	//好的接下来我们将对矩阵初始化
	int arr[50][50] = { 0 };
	int i, j;
	for (i = 0; i < n; i++)
	{
		for (j = 0; j < n; j++)
		{
			arr[i][j] = i + j + 1;
			printf("%d ", arr[i][j]);
		}
		printf("\n");
	}
	return 0;
}
           
5e f5 d3