【那些年那些题】杨氏矩阵查找目标数

题目描述：

有一个数字矩阵，矩阵的每行从左到右是递增的，矩阵从上到下是递增的，请编写程序在这样的矩阵中查找某个数字是否存在。

要求：时间复杂度小于O(N);

思路分析：

最简单粗暴的查找方法就是逐个元素进行遍历，但是这样时间复杂度是O(N)，不满足题目要求，所以需要观察这个杨氏矩阵具备什么样的特性或者规逻辑规律。

 每一行的第一个数为该行最小的数，如果这个数仍比要找的数大那么这一行就没有要找的数（每一列也是同理）；每一行的最后一个数为该行最大的数，如果这个数仍比要找的数小，那么这一行就没有数比要找的数大（每一列也是同理）。

 所以我们只需要先利用排除一行（列）的特性，缩小查找范围，然后再逐个元素进行查找即可。同时也满足了时间复杂度小于O(N)的条件。

编程逻辑：

 从第一行最后一列开始比较，如果第一行最后一列的数小于要查找的数，那么直接用下一行最后一列的数进行比较；如果第一行最后一列的数大于要查找的数，那么列数就减一，再次进行比较，这里就是逐元素进行比较了。

 当然，我们也可以从最后一行第一列开始比较，逻辑方法是一样的。

代码实现：

void find_num(int a[3][3], int key, int c, int r) {
  int i = 0;
  int j = r - 1;
  int flag = 1;
  while (i < c && j >= 0) {
    if (a[i][j] < key) {
      i++;
    }
    else if (a[i][j] > key) {
      j--;
    }
    else {
      flag = 0;
      printf("找到了，下标是%d,%d", i, j);
      break;
    }
  }
  if (flag)
    printf("找不到！");
}
int main() {
  int a[3][3] = { 1,2,3,4,5,6,7,8,9 };
  int key;
  scanf("%d", &key);
  find_num(a, key, 3, 3);
  return 0;
}