杨氏矩阵

有一个二维数组. 数组的每行从左到右是递增的，每列从上到下是递增的.

在这样的数组中查找一个数字是否存在。 时间复杂度小于O(N);

数组：

1  2  3 　　　　  1  3  4 　　　　  1  2  3

2  3  4  　　　　 2  4  5  　　　　 4  5  6

3  4  5   　　　　4  5  6  　　　　 7  8  9

1 #include
     
       2  3 #define ROW 3 4 #define COL 3 5  6 int Find_num(int arr[ROW][COL],int num) 7 { 8     //从右上角开始查询 9     int row = 0;10     int col = COL - 1;11     while (row < ROW && col
      
        num)14         {15             //查询左边的数16             --col;17         }18         if (arr[row][col] < num)19         {20             //查询下一行21             ++row;22         }23         if (arr[row][col] == num)24         {25             break;26         }27     }28     if (arr[row][col] == num)29     {30         return 1;31     }32     else33     {34         return 0;35     }36 }37 38 int main()39 {40     //要求时间复杂度小于=O(N)，则可以利用杨氏矩阵的一些特性41     //如果将每一个都数都查找一遍，则最长时间应该为O(row * col)42     //如果利用每行从左到右是递增的，每列从上到下是递增的这一性质则为O(row + col)43     int arr[ROW][COL] = { 1,2,3,3,4,5,4,5,6};44     int num = 0;45     while (1)46     {47         printf("请输入您要查找的数字：\n");48         scanf("%d", &num);49         int find_num = Find_num(arr, num);50         if (find_num == 0)51         {52             printf("数字不存在！\n");53         }54         else55         {56             printf("数字存在！");57         }58 59     }60 61     return 0;62 }