楊氏矩陣（判斷某個數字是否存在）

有一個數字矩陣，矩陣的每行從左到右是遞增的，矩陣從上到下是遞增的， 請編寫程式在這樣的矩陣中查找某個數字是否存在。

要求：時間複雜度小于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;
}