问题描述：
有一个数字矩阵，矩阵的每行从左到右是递增的，矩阵从上到下是递增的，请编写程序在这样的矩阵中查找某个数字是否存在,且程序的时间复杂度要小于O(N);
问题分析：
经过初步分析后我们可以发现，这道题可以通过遍历数组的办法解决。
问题解决：
方法一：
由于代码过于简单我们直接上代码就行：
int find(int (*p)[4], int row, int col, int put) { bool flag = false; for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) { if (*(*(p + i) + j) == put) { printf("找到了，它位于矩阵的第%d行，第%d列\n", i + 1, j + 1); flag = true; break; } } } if (flag == false) { printf("该数不在矩阵中，请重新输入\n"); } } int main() { int i = 0; int arr[3][4] = { {1,2,3,4} ,{5,6,7,8},{9,10,11,12} }; printf("请输入要查找的数字："); while ((scanf_s("%d", &i)) != EOF) { find(arr, 3, 4, i); } return 0; }
方法二：
方法一虽然可以得到正确结果，但是问题也很明显，就是我们每次查找都需要重新遍历一次数组，如果数组元素较少还可以接收，但是如果数组元素过多就会降低查找效率不能满足时间复杂度小于O(N)的题目要求，所以我们想到了方法二。
我们仔细分析，不难发现，对于杨氏矩阵来说，右上角和左下角的元素是有特点的:右上角的元素是一行中最大的，一列中最小的。左下角的元素是一行中最小的，是一列中最大的。所以我们可以从右上角或者左下角开始查找。
比如：从右上角开始查找的时候，右上角的元素比我们要查找元素小，我们就可以去掉右上角元素所在的这一行；右上角的元素比我们要查找的元素大，我们就可以去掉右上角元素所在的这一列。然后依然找右上角的元素继续和要查找的元素与比较。这样每一次比较去掉一行或者去掉一列。这个查找效率是高于遍历数组元素的，所以时间复杂度是小于O(N)，也满足题目要求。
步骤一：在主函数中创建一个二维数组
int arr[][3] = {{1,3,5},{3,5,7},{6,7,9}}
步骤二：创建查找函数find
void find(int (*a)[3], int row ,int col ,int findnum) { int i = 0; int j = row - 1； while(j >=0 && i < row) //col>=0 确保数组列数不为0，i<row方便下面的排查不会越界 { if(*(a+i)[j] < findnum) //如果查找位置小于findnum { i++； //行数加一，向下一行查找 } else if(*(a+i)[j] > findnum) //如果查找位置大于findnum { j--; //列数减一，向上一列查找 } else { return 1; } } }
通过画图，我们不难发现右上角元素在二维数组中元素下标总是数组行数减一：
步骤三：完善主函数
int main() { int a[][3] = { {1, 3, 5}, {3, 5, 7}, {5, 7, 9} }; if (find(a, 3, 3, 2)) //只有当找到时返回值等于1是真，显示找到，否则显示未找到 { printf("It has been found!\n"); } else { printf("It hasn't been found!\n"); } return 0; }
整体代码如下：
int find(int (*a)[3], int row, int col, int findnum) { int i = 0, j = col - 1; while (j >= 0 && i < row) { if ((*a+i)[j] < findnum) { i++; } else if (*(a+i)[j] > findnum) { j--; } else { return 1; } } return 0; } int main() { int a[][3] = { {1, 3, 5}, {3, 5, 7}, {5, 7, 9} }; if (find(a, 3, 3, 2)) { printf("It has been found!\n"); } else { printf("It hasn't been found!\n"); } return 0; }
