一魚多吃 用一維的二元搜搜尋模型來解 Search a 2D Matrix_Leetcode #74

題目在這裡:

題目會給我們一個排序好的矩陣matrix ，和一個目標值 target

題目要求必須在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.length
• n == matrix[i].length
• 1 <= 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