使用这两种方法在二维矩阵中查找目标值的时间复杂度是否相同？

Question

leetcode 问题 要求在二维矩阵中搜索目标值。两种方法都使用二进制搜索。

我的做法：

将矩阵视为长度为

rows x columns

的单个数组，然后使用整数除法和模数在二分查找中得到

row

和

column

索引。这个的时间复杂度是

O(log [rows x colums])

# Binary search on rows and then on columns
# Time : O(log nm) # binary search on total numbers of cells
# Space : O(1) # same number of pointers (left, right, mid) regardless of size of matrix
from typing import List
class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        ROWS = len(matrix)
        COLUMNS = len(matrix[0])

        left = 0
        right = ROWS * COLUMNS - 1 


        # run regular binary search as if dealing with just an array
        while left <= right: # <= handles case when left, right are the same and value not considered before
            mid = left + ( (right - left) // 2 )
            row = mid // COLUMNS
            col = mid %  COLUMNS # has to be COLUMNS and not ROWS. 
            # Try [[1,1]] with ROWS, will get index-out-of-range error

            # print(f"left = {left} right = {right} mid = {mid} row = {row} col = {col}")
            if target < matrix[row][col]:
                right = mid - 1
            elif target > matrix[row][col]:
                left = mid + 1
            else:
                return True

        # not found
        return False

Neetcode的做法：

然后我碰到了neetcode的解决方案视频，他在那里消除了

rows

，然后只关注可能包含目标的

row

。因为先排除行，然后再搜索可能行的列，所以时间复杂度为

O( log[rows] + O[columns] )

.

# Binary search on rows and then on columns
# Time : O(log n + log m) # binary search on rows then on columns
# Space : O(1) # same number of pointers (top, bottom, row, left, right) regardless of size of matrix
from typing import List
class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        ROWS = len(matrix)
        COLUMNS = len(matrix[0])

        top = 0
        bottom = ROWS - 1

        while top <= bottom:
            row = top + ((bottom-top)//2)

            if target < matrix[row][0]:
                bottom = row - 1
            elif target > matrix[row][-1]:
                top = row + 1
            else:
                # break so you can retain row value and check within the row
                break 

        # ambiguous here: could have ended here because 
        # of the break in the while loop or the while 
        # condition failed so check
        if top > bottom:
            return False

        # check within the row. 2nd binary search
        left = 0
        right = COLUMNS - 1
        
        while left <= right:
            # avoid overflow in other languages
            mid = left + ((right - left) // 2)

            if target < matrix[row][mid]:
                right = mid - 1
            elif target > matrix[row][mid]:
                left = mid + 1
            else:
                return True
        
        return False

在试图弄清楚什么是大 O 表示法中的最佳时，我想到它们可能是相同的，因为

log(xy) = log(x) + log(y)

在数学中。它们本质上是一样的吗？