題目出處

74. Search a 2D Matrix

難度

medium

題目分類

Array, Binary Search, Matrix

個人範例程式碼

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        m = len(matrix)
        n = len(matrix[0])
        l = 0 # left
        r = m*n-1 # right

        # matrix[idx//n][idx%n]
        while(l <= r):
            mid = (l+r)//2
            if matrix[mid//n][mid%n] == target: # found
                return True
            elif matrix[mid//n][mid%n] < target: # mid smaller than target
                l = mid+1
            else: # mid bigger smaller than target
                r = mid-1

        return False

Time Complexity

O(logN)

Space Complexity

O(1)

算法說明

「查詢」的重要概念

這題帶出了「查詢的重要觀念」，
查詢這件事情基本上的時間複查度，

通常一般會是：

• O(n): 每一個都看過
• O(1): 有 hash map，用空間換取時間

這裡要來講一個特別的情況，當我們發現這個要查找的內容「有序或有規律」可尋，
也就是說，只要他「不是完全雜亂的」，
我們可以嘗試使用 binary search = O(logN)

這題目很明顯已經排好順序了，我們可以每次很輕鬆的進行對半切的動作，
這樣的概念就是「binary search」，之後在 tree 會更常使用。

處理成一維陣列

我們處理的重點就是在 binary search，
我們直接把這個矩陣當一個一維陣列來看，轉換方式為：

m = len(matrix)
n = len(matrix[0])

而 matrix[idx//n][idx%n] 的 idx 就可以代表我們想要的位置。

尋找過程

l = 0 # left
r = m*n-1 # right

我們找 mid = (l + r) //2

• 當 matrix[mid] target， 找到了!
• 當 matrix[mid] > target，我們比目標大，mid – 1
• 當 matrix[mid] < target， 我們還是比目標小，mid + 1

然後重複濃縮 mid 的範圍

直到 l >= r (因為一直有 +1 -1的操作)，遲早會重疊。

corner case 特殊情況處理

當只有一行時，需要注意處理 idx+1，idx-1 都會出錯

Boundary conditions/ Edge conditions 邊際情況處理

計算到 l >= r (因為一直有 +1 -1的操作)，遲早會重疊。

Reference

• Don’t treat it as a 2D matrix, just treat it as a sorted list