杨氏矩阵算法

问题：已知一个2维矩阵，其中的元素每一行从左至右依次增加，每一列从上到下依次增加。即对于矩阵Table有Table[i][j] ≤Table[i][j + 1], Table[i][j] ≤ Table[i + 1][j]，我们也称这样的矩阵为杨氏矩阵。给出判定某个数是否存在该矩阵中的高效算法。

话不多说，我们直接举例：

首先我们创建一个二维数组：

int arr[3][3] = { {1,2,3},{4,5,6},{7,8,9} };

其矩阵分布如下图所示：

可以看到，右上角的元素3是一个特殊元素，它是它这一行中最大的元素，它这一列中最小的元素。所以我们可以通过把所要寻找的元素和右上角的元素比较一下就可以排除一行或者一列。这里我们假如要寻找的数字是7，那么我们首先零x=0,y=2,然后跟3比较，比较后排除第一列然后x++,y不变 这时指向的数字是6，我们再跟6比较又排除了一行，此时x++,y不变。然后跟9比较，x不变,而y--以此类推，最后找到7.

代码实现：

int FindNum(int arr[3][3], int k, int* px, int* py) {
	int x = 0;
	int y = *py - 1;
	while (x <=2 &&y >= 0) {
		if (k > arr[x][y]) {
			x++;
		}
		else if (k < arr[x][y]) {
			y--;
		}
		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 = 7;
	int x = 3;
	int y = 3;
	int ret = 0;
	ret = FindNum(arr, k, &x, &y);
	if (1 == ret) {
		printf("找到了！\n");
		printf("坐标是：%d,%d", x, y);
	}
	else {
		printf("Fail!\n");
	}
	return 0;

}