杨氏矩阵（详解）_小杨做题日字矩阵

题目：

有一个数字矩阵，矩阵的每行从左到右是递增的，矩阵从上到下是递增的，请编写程序在这样的矩阵中查找某个数字是否存在。要求：时间复杂度小于O(N);

代码实现：

#include<stdio.h>
int find_num(int arr[3][3], int* px, int* py, int k)
{
	int x = 0;
	int y = *py - 1;
	while (x<= *px && y>= 0)
	{
		if (arr[x][y] > k)
		{
			y--;
		}
		else if (arr[x][y] < k)
		{
			x++;
		}
		else
		{
			*px = x;
			*py = y;
			return 1;
		}
	}
	return 0;
}
int main()
{
	int arr[3][3] = { 1,2,3,4,5,6,7,8,9 };
	int k = 0;
	scanf("%d", &k);
	int x = 3;
	int y = 3;
	int ret = find_num(arr,&x,&y, k);
	if (ret == 1)
	{
		printf("找到了,坐标是: %d %d\n", x, y);
	}
	else
	{
		printf("找不到\n");
	}
	return 0;
}

大致思路：

杨氏矩阵：

1 2 3

4 5 6

7 8 9

比如要查找数字7，方法：

1 从右上角（or左下角）的数字开始，因为右上角的数字是一行的最大值，一列的最小值（左下角的数字是一行中的最小值，一列中的最大值）

2 比较右上角的数字与要查找的数字：

   a. 若右上角的数字>被查找的数字：y--（y代表列的序号）能去掉一列

   作为一列中的最小值都比被查找的数字大，则这一列中肯定不能找到被查找的数字

   b. 若右上角的数字<被查找的数字：x++（x代表行的序号）能去掉一行

  作为一行中的最大值都比被查找的数字小，则这一行中肯定不能找到被查找的数字

   c. 若相等，则找到了，返回此数字的坐标

       这里使用了一个很妙的操作：将代表行数的x，列数的y的地址传给函数，做到了既输入又输出

        输入：把行数和列数传入参数

        输出：通过指针改变实参x，y，将被查找数字的下标带回