一魚多吃 用一維的二元搜搜尋模型來解 Search a 2D Matrix_Leetcode #74
題目在這裡:
題目會給我們一個排序好的矩陣matrix ，和一個目標值 target
要求我們在矩陣中尋找target，如果存在，返回True。
如果target 不存在，返回False
題目要求必須在O( log (m*n) )對數時間內完成 。
測試範例:
Example 1:
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true
Example 2:
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false
約束條件:
Constraints:
m == matrix.lengthn == matrix[i].length1 <= m, n <= 100-104<= matrix[i][j], target <= 104
演算法:
題目的輸入矩陣已經保證升序排列，排序好。
一維的二分搜尋法我們已經在前面學過，可以用中心點剖半的方法去尋找。
其實，高維度的版本觀念也是相通的。
在思考觀點上，既然矩陣已經排序好，更何況矩陣預設在記憶體內的分布還是Row major的形式，也就是下一排的Row會排在上一排的Row之後。
重點: 其實，我們可以把二維矩陣視為一個重新排過形狀的一維矩陣。
這樣一來，我們就把二維排序好的矩陣搜尋問題，化簡到一維排序好的陣列搜尋問題。再用原本原本已經會的Binary Search 來反推原本二維搜尋的答案。
原本的二維矩陣搜尋的視角:
化簡為等價的 一維陣列搜尋的視角:
這種演算法化簡的技巧，在演算法理論也稱之為Reduction，
把一個新的問題A，映射到一個已經知道解法(演算法)的問題B，再透過已知問題B的解答反推問題A的答案。
演算法九成都一樣，唯一一個不同是，我們要記得做座標轉換，
畢竟原本的輸入矩陣是二維，計算時，需要把index映射回原本的二維座標
h, w = len(matrix), len(matrix[0])
left, right = 0, h * w - 1
while left <= right:
mid = left + (right - left) // 2
row, col = divmod(mid, w)
mid_value = matrix[row][col]
程式碼:
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
if not matrix or not matrix[0]:
# Quick response on empty input matrix
return False
h, w = len(matrix), len(matrix[0])
left, right = 0, h * w - 1
while left <= right:
mid = left + (right - left) // 2
row, col = divmod(mid, w)
mid_value = matrix[row][col]
if mid_value == target:
return True
elif mid_value > target:
right -= 1
else:
left += 1
return False
時間複雜度:
O( log mn ) , 可以從 T(N) = T(N/2) + O(1) 用Master Theorem推導而來
其中 N = m * n = 高 * 寬 = 對應等價一維陣列的總長度
空間複雜度:
迭代法為O(1)，相當於指使用雙指針double pointers，所耗費的空間成本固定，為常數級別O(1)
學完這題的同學，強烈建議回去複習一維版本的Binary Search，其實背後的原理和演算法框架都是相通的喔!
Reference:
[1] Python/Go/JS/C++ O(log mn) binary search [w/ Visualization] - Search a 2D Matrix - LeetCode
