---
title: "74. Search a 2D Matrix"
url: "https://laigary.com/interview/coding/74-search-a-2d-matrix"
type: "note"
section: "coding"
date: "2024-08-14"
updated: "2026-07-26"
tags: ["Array", "Binary Search"]
---

# 74. Search a 2D Matrix

[74\. Search a 2D Matrix](https://leetcode.com/problems/search-a-2d-matrix/)

在一個矩陣裡找 `target`。矩陣的性質是：**每一列由左到右遞增，而且每一列的第一個數字都大於上一列的最後一個數字。**

## 思路

題目那兩個條件加起來其實在說一件事：

> **把整個矩陣一列一列接起來，就是一個完全排序的一維陣列。**

一旦看穿這點，題目就從「二維搜尋」變回「**在排序陣列上二分搜尋**」—— 一個已經會的問題。剩下的只是索引換算。

這是這題最重要的一步：**先問「這個資料結構等價於什麼我已經會的東西」**，而不是急著設計二維的搜尋策略。

### 索引怎麼換算

把一維索引 `idx` 對應回二維座標，用 `cols`（每列的長度）做除法和取餘：

- `row = idx // cols` —— 走過幾個完整的列
- `col = idx % cols` —— 在那一列的第幾個

反過來 `idx = row * cols + col`。這組換算在很多「把二維攤平成一維」的題目都會用到。

**注意除數是 `cols` 不是 `rows`**，這是最容易寫反的地方 —— 想成「每前進 `cols` 個元素就換一列」就不會錯。

## 解題方向

```python
class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        rows = len(matrix)
        cols = len(matrix[0])

        def getVal(idx):
            row = idx // cols
            col = idx % cols
            return matrix[row][col]
        left = 0
        right = rows * cols - 1

        while left <= right:
            mid = left + (right - left) // 2
            if getVal(mid) == target:
                return True
            elif getVal(mid) > target:
                right = mid - 1
            elif getVal(mid) < target:
                left = mid + 1
        
        return False
```

把換算包成 `getVal` 是很好的做法：**二分搜尋的邏輯完全沒被二維的細節污染**，跟一維版本長得一模一樣。面試時這樣寫也比較好解釋 —— 先說「我把它當成長度 `rows * cols` 的排序陣列」，再說「`getVal` 負責把索引翻譯回座標」。

用的是**左閉右閉**區間（`right = n - 1`、`while left <= right`、`right = mid - 1`），三個地方要一致。邊界寫法固定一種練到閉著眼睛都不會錯，見 [Binary Search 模板](/interview/coding/binary-search-template)。

`mid = left + (right - left) // 2` 而不是 `(left + right) // 2` 是為了避免整數溢位 —— Python 的整數無上限所以不影響，但在 Java / C++ 是必要的，寫成這樣是好習慣。

## 補充

**別和 [240. Search a 2D Matrix II](/interview/coding/240-search-a-2d-matrix-ii) 搞混。** 兩題長得很像但**條件不同**，導致解法完全不同：

| | 矩陣性質 | 能不能攤平成一維 | 解法 | 複雜度 |
|---|---|---|---|---|
| **74 這題** | 每列遞增，**且下一列的開頭 > 上一列的結尾** | **可以** | 一次二分 | $O(\log(mn))$ |
| 240 | 每列遞增、每行遞增，**但列與列之間沒有保證** | **不行** | 從右上角往左下走 | $O(m + n)$ |

240 之所以不能攤平，是因為 `[[1,4],[2,5]]` 這種矩陣攤平成 `[1,4,2,5]` 並不是排序的。**讀題時要特別確認是哪一種**，這是這兩題最常見的混淆點。

240 的解法也很漂亮：從右上角出發，比 target 大就往左（整行排除）、比 target 小就往下（整列排除），每一步都能刪掉一整行或一整列。

**其他二分搜尋題**：[704. Binary Search](/interview/coding/704-binary-search)（最基本的模板）、[35. Search Insert Position](/interview/coding/35-search-insert-position)、[33. Search in Rotated Sorted Array](/interview/coding/33-search-in-rotated-sorted-array)（旋轉過的陣列）。

## 複雜度

- 時間 $O(\log(mn))$ — 對長度 `m × n` 的虛擬一維陣列做二分；也可以寫成 $O(\log m + \log n)$，兩者相等
- 空間 $O(1)$ — 只有幾個索引變數，沒有真的把矩陣攤平成新陣列

其中 `m`、`n` 是矩陣的列數和行數。

**「沒有真的攤平」值得強調**：`getVal` 是即時換算的，所以空間是 $O(1)$。如果真的建一個一維陣列就會變成 $O(mn)$。