题目内容
有一个数字矩阵，矩阵的每行从左到右是递增的，矩阵从上到下是递增的，请编写程序在这样的矩阵中查找某个数字是否存在。
要求：时间复杂度小于O(N);
思路分析
题目中所说的矩阵，大概是这样
1 2 3 4 5
2 3 4 5 6
3 4 5 6 7
4 5 6 7 8
5 6 7 8 9
可以发现，在矩阵里面找数，最基本的方法就是遍历整个数组并判断相等，但这样会发现，矩阵里面有很多重复的数组，如果遍历一遍，效率会低很多，有没有一种高效的方法呢？我们来一起看看，
注意看杨氏矩阵的特点，它的右上角是一行中最大，一列中最小的，且与关联的两条边，会发现它涵盖了矩阵里面所出现的数字，左下角相反，一列中最大，一行中最小的，其实，我们没有必要遍历整个数组，只需要根据我们所定义的起点来遍历外围即可找到所有的数字。
1.以右上角为起点
这里要用一个二维数组来存储整个矩阵，右上角的坐标是arr[0][4]，和它同行比他小，和它同列比他大，如果我们要找的数比他大，就向下遍历，比他小，我就向左遍历，直到找到数字。
代码语言：javascript复制int looking_for(int arr[][5], int x, int y, int k)
{
int i = 0;
int j = y - 1;
while (i < x && j >= 0)
{
if (arr[i][j] < k)
{
i ;
}
else if (arr[i][j] > k)
{
j--;
}
else
{
return 1;
}
}
return 0;
}
int main()
{
int k = 0;
printf("请输入要寻找的数：");
scanf("%d", &k);
int arr[5][5] = { {1,2,3,4,5},{2,3,4,5,6},{3,4,5,6,7},{4,5,6,7,8},{5,6,7,8,9} };
if (looking_for(arr, 5, 5, k))
{
printf("yesn");
}
else
{
printf("non");
}
return 0;
}2.以左下角为起点
与右上角相反，左下角的下标为arr[4][0],和他同行比他大，和它同列比他小，如果我们要找的数比他大，就向右遍历，比他小，我就向上遍历，直到找到数字。
代码语言：javascript复制int looking_for(int arr[][5], int x, int y, int k)
{
int i = x - 1;
int j = 0;
while (j < y && i>=0)
{
if (arr[i][j] < k)
{
j ;
}
else if (arr[i][j] > k)
{
i--;
}
else
{
return 1;
}
}
return 0;
}
int main()
{
int k = 0;
printf("请输入要寻找的数：");
scanf("%d", &k);
int arr[5][5] = { {1,2,3,4,5},{2,3,4,5,6},{3,4,5,6,7},{4,5,6,7,8},{5,6,7,8,9} };
if (looking_for(arr, 5, 5, k))
{
printf("yesn");
}
else
{
printf("non");
}
return 0;
}
