74. 搜尋二維矩陣（Search a 2D Matrix）

• 題解
• • 兩次二分查找
  • • 複雜度分析
    • Python
    • Java（待完成）
  • 一次二分查找
  • • 算法流程
    • 複雜度分析
    • Python
    • Java（待完成）

題解

看到本題矩陣的性質，第一反應是使用兩次二分查找。第一次查詢， t a r g e t target target的所在行。第二次查詢， t a r g e t target target的所在列。

兩次二分查找

1. 特判，若 m a t r i x matrix matrix為空或 m a t r i x [ 0 ] matrix[0] matrix[0]為空，主要應對 [ ] [] []和 [ [ ] ] [[]] [[]]。
2. 初始化矩陣行數 m m m和列數 n n n。
3. 初始化查詢行的左右界， l = 0 l=0 l=0, r = m − 1 r=m-1 r=m−1，當 l < = r l<=r l<=r時進入循環：
   • m i d = ( l + r ) / / 2 mid=(l+r)//2 mid=(l+r)//2，若最後一行中 m a t r i x [ m i d ] [ n − 1 ] = = t a r g e t matrix[mid][n-1]==target matrix[mid][n−1]==target，直接傳回 T r u e True True
   • 如果 m a t r i x [ m i d ] [ n − 1 ] > t a r g e t matrix[mid][n-1]>target matrix[mid][n−1]>target，令 r = r − 1 r=r-1 r=r−1
   • 否則，令 l = l + 1 l=l+1 l=l+1
4. 若查詢行的左界 l > m − 1 l>m-1 l>m−1，說明 t a r g e t target target大于所有數組元素，傳回 F a l s e False False。
5. 在 l l l行内，進行搜尋，初始化查詢列的左右界， l _ 2 = 0 l\_2=0 l_2=0, r _ 2 = n − 1 r\_2=n-1 r_2=n−1，當 l _ 2 < = r _ 2 l\_2<=r\_2 l_2<=r_2時進入循環：
   • m i d _ 2 = ( l _ 2 + r _ 2 ) / / 2 mid\_2=(l\_2+r\_2)//2 mid_2=(l_2+r_2)//2，在 i i i行中 m a t r i x [ i ] [ m i d _ 2 ] = = t a r g e t matrix[i][mid\_2]==target matrix[i][mid_2]==target，直接傳回 T r u e True True
   • 如果 m a t r i x [ i ] [ m i d _ 2 ] > t a r g e t matrix[i][mid\_2]>target matrix[i][mid_2]>target，令 r _ 2 = r _ 2 − 1 r\_2=r\_2-1 r_2=r_2−1
   • 否則，令 l _ 2 = l _ 2 + 1 l\_2=l\_2+1 l_2=l_2+1。
6. 傳回 F a l s e False False。

複雜度分析

• 時間複雜度： O ( log ⁡ ( m n ) ) O(\log (mn)) O(log(mn))。查找所在行 O ( log ⁡ ( m ) ) O(\log (m)) O(log(m))，查找所在列 O ( log ⁡ ( n ) ) O(\log (n)) O(log(n)) 。總體 O ( log ⁡ ( m ) ) + O ( log ⁡ ( n ) ) = O ( log ⁡ ( m n ) ) O(\log (m))+O(\log (n))=O(\log (mn)) O(log(m))+O(log(n))=O(log(mn))
• 空間複雜度： O ( 1 ) O(1) O(1)

Python

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        if(not matrix or not matrix[0]):
            return False
        m=len(matrix)
        n=len(matrix[0])
        l=0
        r=m-1
        while(l<=r):
            mid=(l+r)//2
            if(matrix[mid][n-1]==target):
                return True
            elif(matrix[mid][n-1]>target):
                r=r-1
            else:
                l=l+1
        if(l>m-1):
            return False
        l_2=0
        r_2=n-1
        while(l_2<=r_2):
            mid_2=(l_2+r_2)//2
            if(matrix[l][mid_2]==target):
                return True
            elif(matrix[l][mid_2]>target):
                r_2-=1
            else:
                l_2+=1
        return False
           

Java（待完成）

一次二分查找

有點二維數組壓縮的感覺。參考官方題解，發現可将二維矩陣映射到一維上。圖檔來自官方題解。

由圖可知，一位數組中索引為 i d x idx idx對應二維矩陣中 r o w row row， c o l col col位置的元素，對應關系如下：

行 r o w = i d x / / n row = idx // n row=idx//n

列 c o l = i d x col = idx % n col=idx

算法流程

1. 特判，若 m a t r i x matrix matrix為空或 m a t r i x [ 0 ] matrix[0] matrix[0]為空，主要應對 [ ] [] []和 [ [ ] ] [[]] [[]]。
2. 初始化矩陣行數 m m m和列數 n n n。初試化查詢左右界 l = 0 l=0 l=0， r = m ∗ n − 1 r=m*n-1 r=m∗n−1。
3. 循環條件，當 l < = r l<=r l<=r時進入循環：
   • m i d = ( l + r ) / / 2 mid=(l+r)//2 mid=(l+r)//2，若 m a t r i x [ m i d / / n ] [ m i d % n ] = = t a r g e t matrix[mid//n][mid\%n]==target matrix[mid//n][mid%n]==target，直接傳回 T r u e True True
   • 如果 m a t r i x [ m i d / / n ] [ m i d % n ] > t a r g e t matrix[mid//n][mid\%n]>target matrix[mid//n][mid%n]>target，令 r = r − 1 r=r-1 r=r−1
   • 否則，令 l = l + 1 l=l+1 l=l+1
4. 傳回 F a l s e False False

複雜度分析

• 時間複雜度： O ( M ∗ N ) O(M*N) O(M∗N)
• 空間複雜度： O ( 1 ) O(1) O(1)

Python

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        if(not matrix or not matrix[0]):
            return False
        m=len(matrix)
        n=len(matrix[0])
        l=0
        r=m*n-1
        while(l<=r):
            mid=(l+r)//2
            if(matrix[mid//n][mid%n]==target):
                return True
            elif(matrix[mid//n][mid%n]>target):
                r=r-1
            else:
                l=l+1
        return False
           

Java（待完成）