今天来向大家介绍一个用C语言实现杨氏矩阵的问题。题目如下：
有一个数字矩阵，矩阵的每行从左到右是递增的，矩阵从上到下是递增的，请编写程序在这样的矩阵中查找某个数字是否存在。
要求：时间复杂度小于O(N);
题干中所描述的矩阵被称作杨氏矩阵，然后让你在这个这个矩阵中查找一个数字。其实在矩阵中查找一个数字并不难，只需采取遍历的方式，将矩阵中每个元素拿出来比较即可。但这道题还有一个要求就是时间复杂度必须小于O（N）,也就是说不能采用遍历的方式来查找。因此我们需要根据杨氏矩阵的特点来写一个新的算法进行查找。
如下图所示，为一个3x3的杨氏矩阵。
根据题目我们总结一下杨氏矩阵的两个特点：
1. 同一行的元素由左向右依次递增
2. 同一列的元素从上到下依次递增
通过这两点我们会发现这个矩阵有两个元素是特殊元素。
因此我们可以采用以下方法：
先拿出右上角的元素3来和所查找的元素比较，如果3比要查找的元素大，那说明该元素绝不可能在第一行，因此我们就可以直接排除一行的元素。如果3比要查找的元素小，那说明该元素绝不可能在最后一列，因此我们就可以直接排除一列的元素
现在假设我们排除了一行的元素，那接下来的矩阵就变成了这样：
这时6又变成了右上角的元素，然后重复上一步的操作，假设我们这次排除了一列的元素，那接下来的矩阵就变成了这样：
于是5变成了右上角的元素，继续重复上一步操作，这样每一次查找我们都可以排除一行或者一列的元素，大大的提高了算法效率。
当然上述举例我是以右上角元素为基准的，如果以左下角元素为基准也可以得到相同的结果，大家不妨自己来试一下。
实现代码如下：
#include <stdio.h>
int find_num(int arr[3][3], int row, int col, int k)
{
int x = 0;
int y = col-1;
while (x<row && y>=0)
{
if (arr[x][y] == k)
{
printf("下标为： %d %d\n", x, y);
return 1;
}
else if (arr[x][y] > k)
y--;
else if (arr[x][y] < k)
x++;
}
return 0;
}
int main()
{
int arr[3][3] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
int ret = find_num(arr, 3, 3, 7);
if (ret == 1)
printf("找到了\n");
else
printf("找不到\n");
return 0;
}
这里我们将查找杨氏矩阵元素的过程封装在一个函数中。函数接收4个参数，分别是二维数组的地址，行数，列数和要查找的元素。通过返回值来判断是否找到。
在函数内部定义一个坐标（x, y）表示右上角元素，当x等于行数是说明已经越界(数组下标是从0开始的)，那要查找的元素必然不存在。当列数小于0也一样。
当排除一行的时候，给x的值加1即可；排除一列的时候，给y的值减1即可。
运行结果：
