在一個
m x n矩陣中搜尋目標值target。矩陣性質：每列由左到右遞增、每行由上到下遞增（注意：不像 74 那樣整體展平後有序，行尾不一定小於下一行行首）。
Example:
Input: matrix = [[ 1, 4, 7,11,15], [ 2, 5, 8,12,19], [ 3, 6, 9,16,22], [10,13,14,17,24], [18,21,23,26,30]], target = 5 Output: true
Input: 同上, target = 20 Output: false
Intuition
TIP
核心思路：從右上角出發。該位置是所在列的最大、所在行的最小——比 target 大就往左砍一整列尾、比 target 小就往下砍一整行頭，每步排除一行或一列。
- 右上角
matrix[0][n-1]：往左值變小、往下值變大，方向明確不分岔 cur > target→ 這一行右側都更大 →col--cur < target→ 這一列上方都更小 →row++- 每步必排除一整列或一整行，最多
m + n步
Approaches
1. Binary Search Each Row — O(m log n) / O(1)
- Idea: 每列都有序，逐列二分找 target
- Time:
O(m log n)- m 列、每列二分O(log n) - Space:
O(1)
class Solution {
fun searchMatrix(matrix: Array<IntArray>, target: Int): Boolean {
for (row in matrix) {
var lo = 0; var hi = row.size - 1
while (lo <= hi) {
val mid = (lo + hi) ushr 1
when {
row[mid] == target -> return true
row[mid] < target -> lo = mid + 1
else -> hi = mid - 1
}
}
}
return false
}
}⭐ 2. Staircase Search from Top-Right — O(m + n) / O(1)
- Idea: 利用「右上角往左變小、往下變大」每步排除一行或一列
- Time:
O(m + n)- 每步 row++ 或 col— - Space:
O(1)
class Solution {
fun searchMatrix(matrix: Array<IntArray>, target: Int): Boolean {
if (matrix.isEmpty() || matrix[0].isEmpty()) return false
var row = 0
var col = matrix[0].size - 1
while (row < matrix.size && col >= 0) {
val cur = matrix[row][col]
when {
cur == target -> return true
cur > target -> col-- // 排除這一行右側
else -> row++ // 排除這一列上方
}
}
return false
}
}🔑 Takeaways
- Pattern: 利用二維單調性的階梯（staircase）搜尋，從「方向不分岔」的角落出發
- Key trick: 選右上角（或左下角）當起點是關鍵——左上/右下兩方向都同增同減無法決策。對照 74：那題整體展平有序可純二分
O(log mn)，本題只有行列各自有序故O(m+n)