一、題目介紹
今天要解的題目是LeetCode的Search a 2D Matrix，中文可以稱為「搜尋二維矩陣」。

題目會給定一個m × n的二維矩陣matrix，矩陣具有以下特性

1. 每一列的數字由左到右按照遞增順序排列。
2. 每一列的第一個數字，都大於前一列的最後一個數字。

例如
[
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 60]
]

如果要搜尋target = 3
因為3存在於矩陣中，所以答案為true

如果搜尋target = 13
矩陣中沒有13，因此false

二、解題思路
這題有一個很重要的觀察
雖然矩陣長這樣
[1, 3, 5, 7]
[10, 11, 16, 20]
[23, 30, 34, 60]

但如果把它從左到右、從上到下排列，可以想成
1 → 3 → 5 → 7 → 10 → 11 → 16 → 20 → 23 → 30 → 34 → 60

這其實就是一個已排序的一維陣列

因此可以使用Binary Search
假設矩陣有
m = rows
n = columns
總共有m × n個元素

我們可以把這些元素想像成編號
index = 0, 1, 2, 3, ..., m × n - 1
然後使用Binary Search找到中間位置mid

接著將一維位置轉換回二維座標
row = mid / n
col = mid % n

在Java中
int row = mid / cols; int col = mid % cols;

在Python中
row = mid // cols col = mid % cols

三、解題流程
以以下矩陣為例
[
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 60]
]

搜尋target = 16
矩陣共有3 × 4 = 12個元素
因此可以將它視為[1, 3, 5, 7, 10, 11, 16, 20, 23, 30, 34, 60]

Binary Search一開始
left = 0
right = 11

計算中間位置 mid = 5

對應到矩陣
row = 5 / 4 = 1
col = 5 % 4 = 1
所以matrix[1][1]= 11

因為11 < 16
所以目標值一定在右邊left = mid + 1

下一次找到 mid = 8
對應
row = 8 / 4 = 2
col = 8 % 4 = 0
得到matrix[2][0] = 23

因為23 > 16
所以搜尋範圍縮小到左邊
最後找到matrix[1][2] = 16

因此true

四、Java實作

五、Python實作

六、時間與空間複雜度
Java

• 時間複雜度：O(log(m × n))
  • 矩陣共有：m × n個元素。
  • 因為使用Binary Search，每次都可以將搜尋範圍縮小一半，因此時間複雜度為：O(log(m × n))
  • 也可以寫成：O(log m + log n)，兩種表示方式在這裡是等價的。
• 空間複雜度：O(1)
  • 只使用left、right、mid、row、col等少量變數，沒有建立額外的資料結構。
  • 因此空間複雜度為：O(1)

Python

• 時間複雜度：O(log(m × n))
  • 每一次Binary Search都會將搜尋範圍縮小一半，因此時間複雜度為：O(log(m × n))
• 空間複雜度：O(1)
  • 除了幾個用來記錄搜尋範圍與座標的變數之外，沒有使用額外的資料結構，因此為：O(1)

七、Java與Python解法比較

八、實作結果
Leetcode測試結果：Accepted

九、今日學習心得
今天學習的是Search a 2D Matrix，也是繼Day 05之後再次使用Binary Search。

與Day 05的一維Binary Search相比，今天最大的不同是資料從一維陣列變成了二維矩陣，因此一開始看到題目時，可能會覺得搜尋範圍變得比較複雜。

但仔細觀察矩陣的排列方式後，可以發現每一列以及每一列之間都具有遞增關係，因此可以將整個二維矩陣視為一個排序好的一維資料，再使用Binary Search進行搜尋。

這題讓我學到一個重要的解題技巧：遇到二維資料時，不一定只能用二維的方式思考。 如果能找到資料本身的規律，就可以將問題轉換成自己熟悉的形式。

此外，今天也再次練習了Binary Search的核心概念，以及利用「除法與餘數」將一維索引轉換成二維座標。

透過Day 05和Day 13的比較，我更加理解Binary Search不只是固定的程式碼，而是一種可以應用在不同資料結構上的搜尋方法。