杨式矩阵
有一个数字矩阵，矩阵的每行从左到右是递增的，矩阵从上到下是递增的，请编写程序在这样的矩阵中查找某个数字是否存在
第一种：暴力求解：
直接遍历数组查找每一项
不过这种方法浪费时间
int main() { int arr[3][3] = { 1,2,3,4,5,6,7,8,9 }; int k = 7; int i, j; for (i = 0; i < 3; i++) { for (j = 0; j < 3; j++) { if (arr[i][j] == k) { printf("找到了\n"); return 1;//直接退出 } } } printf("找不到\n"); return 0; }
第二种：二分法求解
第三种：利用特点求解
杨式矩阵的特点：
从左到右是递增的 从上到下也是递增的
那么右上角的数字就有个特点：在一行中是最大值，在一列中是最小值。
所以我们可以从这个数字着手找，如果该数字比所要查找的数字k要大，则这一行中则不可能存在，因为这个一行中该数字最大，所以这行pass掉，再让下一行的最右边的数与查找的数进行比较，如果还是比查找的数字小那么再pass这行，如果比查找的数大，则pass这列，只能在这行的左边找了。依次类推就能找到了。
比如要找的数字是7，右上角的数字是3，3比7小，则pass这行，下一行是6，6比7小，则再找下一行，9比7大，则pass这列，向左找，8比7大，pass这列，最后就找到7了
代码：
#include <stdio.h> int check(int arr[3][3], int* px, int* py, int k) { int x = 0; int y = *py - 1;//右上角数字的坐标 while (x <= *px-1 && y>=0)//循环终止条件 { if (arr[x][y] < k)//如果k比右右上角的数要大，则这行中不可能存在要查找的数，所以找下一行 { x++; } else if (arr[x][y] > k)//如果k比右上角的数小，则这列中不可能存在要查找的数了，只可能在左边 { y--; } else { *px = x; *py = y;//将要查找的数的下标传回去 return 1; } } return 0; } int main() { int arr[3][3] = { 1,2,3,4,5,6,7,8,9 }; int x = 3; int y = 3; int k = 5;//为什么要这样写呢？为什么要传指针过去呢？ ///这样写使得x,y既有输入的功能就可以接收函数返回值可能性 //将函数通过对形参的改变将下标传回来 int ret=check(arr, &x, &y, k); if (ret == 0) { printf("找不到\n"); } else { printf("找到了\n"); printf("下标是 %d %d", x, y); } return 0; }
总结：
对于杨式矩阵，右上角和左下角的元素是有特点的。右上角的元素是一行中最大的，一列中最小的。左下角的元素是一行中最小的，是一列中最大的。所以我们可以从右上角或者左下角开始查找。比如：从右上角开始查找的时候，右上角的元素比我们要查找元素小，我们就可以去掉右上角元素所在的这一行；右上角的元素比我们要查找的元素大，我们就可以去掉右上角元素所在的这一列。然后依然找右上角的元素继续和要查找的元素与比较。这样每一次比较去掉一行或者去掉一列。这个查找效率是高于遍历数组元素的。
