杨氏矩阵详解

题目名称：

杨氏矩阵

题目内容：

有一个数字矩阵，矩阵的每行从左到右是递增的，矩阵从上到下是递增的，请编写程序在这样的矩阵中查找某个数字是否存在。

要求：时间复杂度小于O(N);

思路一： 数组行列递增，是有规律的，所以可以遍历数组寻找数字，但是这题有时间复杂度的要求，遍历数组时间复杂度是O(N*2)，不满足题意。

思路二： 如图所示，矩阵右上角的数字5是它这一行里最大的，是它这一列里的最小的。

矩阵左下角的数字21是它这一行里最小的，是它这一列里的最大的。

 借助这个结论，可以发现，比如要找数字7，它比右上角的数字5大，所以可以排除第一行；比如要找数字23，它比左下角的21大，所以可以排除第一列。

代码如下：

int search(int arr[3][3], int r, int c, int k) { 	int x = 0; 	int y = c - 1; 	while (x < r && c >= 0) 	{ 		if (k > arr[x][y]) 			x++; 		else if (k < arr[x][y]) 			y--; 		else 			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 ret = search(arr,3,3, k); 	if (ret == 1) 		printf("YES\n"); 	else 		printf("NO\n"); 	return 0; }