杨氏矩阵（判断某个数字是否存在）

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

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

例：

1，3，5

2，4，6

3，6，9

#include<stdio.h>
int FindNum(int a[][3], int x, int y, int f)
{
	int i = 0;
	int j = x - 1;
	while (j >= 0 && i < y)
	{
		if (a[i][j] < f)
			i++;
		else if (a[i][j] > f)
			j--;
		else
			return 1;
	}
	return 0;
}
           

由于杨氏矩阵的特点决定了针对表中的任一元素，下方和右方的数据一定大于我，左方和上方的数据一定小于我，所以查找的时候可以利用这一特点，从左上或者右下角来找。因为这两个位置的大于小于是有区分度的。例如我选择从左上角找，那么没有上边和右边，所以下边一定比我大，左边一定比我小，那么要查找的数字如果比我大，那我就向下，如果比我小，那我就向左，这样查找的次数只有x+y-1次，符合题目中要求的O(n)。

int main()
{
	int a[][3] = { {1,3,5},{2,4,6},{3,6,9} };
	int n = 0;
	printf("请输入查找的数:>");
	scanf_s("%d", &n);
	int ret = FindNum(a, 3, 3, n);
	if (ret == 1)
		printf("找到了！\n");
	else
		printf("找不到！\n");

	return 0;
}