#3842. 兔猫信奥学院的“星辰矩阵”探秘

兔猫信奥学院的“星辰矩阵”探秘

🏫 题目名称:兔猫信奥学院的“星辰矩阵”探秘

🐰🐱 题目描述

在兔猫信奥学院的天文观测塔顶,加菲老师布置了一块神秘的“星辰矩阵”——一个 \(m\times n\) 的整数阵列,记录了走廊两端星座的编号。小兔和小猫要在这块矩阵里寻找一颗特定星辰的编号。

这块矩阵满足两条神奇的法则:

  1. 每行从左到右是非严格递增的(允许相邻相等)。
  2. 每行首元素大于上一行的尾元素

加菲老师对他们说:

“给定这块矩阵 matrix 和一个目标编号 target,如果它存在于矩阵中,返回 true;否则返回 false。你需要在 \(O(\log(mn))\) 的时间内完成搜寻!”


📥 输入格式

第一行:三个整数 m, n, target  
接下来 m 行:每行 n 个整数,表示矩阵 matrix[i][0..n-1]
  • \(1 \le m, n \le 100\)
  • \(-10^4 \le matrix[i][j],\;target \le 10^4\)
  • matrix 满足 每行非降行首大于前一行行尾

📤 输出格式

如果 target 存在于矩阵中,输出 true;否则输出 false。

💡 输入输出样例

3 4 3
1  3  5  7
10 11 16 20
23 30 34 60
true
3 4 13
1  3  5  7
10 11 16 20
23 30 34 60
false

📊 数据范围

  • 矩阵行数 \(m\)、列数 \(n\) 最多 100
  • 元素及目标编号在区间 \([-10^4,10^4]\)
  • 要求算法时间复杂度接近 \(O(\log(mn))\)