描述
有一个数字矩阵，矩阵的每行从左到右是递增的，矩阵从上到下是递增的，请编写程序在这样的矩阵中查找某个数字是否存在。
要求
时间复杂度小于O(N)。
1.遍历矩阵 时间复杂度O（N）。
int main() { int a[3][4]={ 1,2,3,5,2,4,6,9,4,6,9,13 }; int b = 0; printf("请输入要查找的数字：\n"); scanf("%d", &b); int x = 0, y = 0;//行 列 for ( x = 0; x < 3; x++) { for (y=0; y < 4; y++) { if (a[x][y] == b) { printf("找到您要查找的数字，其在杨氏矩阵中位于%d行%d列", x+1, y+1); return 0; } } } printf("您要查找的数字不在杨氏矩阵中"); return 0; }
2. 杨氏矩阵每行从左向右递增，每列从上向下递增。
分析：矩阵右上角的元素为一行中的最大值，一列中的最小值。当我们以假设为a的右上角元素要查找的数进行比较，若a大于查找的数，而a又是一列中的最小值，则我们所比较的列数进行左移也就是忽略a所在的列；若a小于查找的数，而a又是一行中的最大值，则我们所比较的行数进行下移也就是忽略a所在的行，如此循环直至剩余一个元素，此算法的时间复杂度小于O(N)。
#include<stdio.h> int main() { int a[3][4]={ 1,2,3,5,2,4,6,9,4,6,9,13 }; int b = 0; printf("请输入要查找的数字：\n"); scanf("%d", &b); int x = 0, y = 3;//行 列 int flog = 0; while (x < 3 && y>0) { if (a[x][y] > b) { y--; } else if (a[x][y] < b) { x++; } else { flog = 1; printf("找到您要查找的数字，其在杨氏矩阵中位于%d行%d列", x+1, y+1); return; } } if (flog == 0) printf("您要查找的数字不在杨氏矩阵中"); return 0; }
3.因所查找的算法行数多可以自定义函数用指针实现。
//查找的数 行数 列数 void yangshi_serach(int a[3][4], int b, int* px, int* py) { int x = 0; int y = *py - 1; while (x<*px&& y>=0) { if (a[x][y] > b) { y--; } else if (a[x][y]< b) { x++; } else { *px = x; *py = y; return; } } *px = - 1; *py = -1; return; } int main() { int a[3][4] = { 1,2,3,5,2,4,6,9,4,6,9,13 }; int b = 0; printf("请输入要查找的数字：\n"); scanf("%d", &b); int x = 3, y = 4;//行 列 int flog = 0; yangshi_serach(a,b,&x,&y); if (x == -1&&y==-1) printf("您要查找的数字不在杨氏矩阵中"); else printf("找到您要查找的数字，其在杨氏矩阵中位于%d行%d列", x + 1, y + 1); return 0; }
