两种二维矩阵二分查找目标值的方法时间复杂度是否一致？

在LeetCode的「搜索二维矩阵」题目中，要求在二维矩阵里查找目标值，以下两种解法都用到了二分查找。

我的方法 #

将矩阵视为长度为rows × columns的一维数组，通过整数除法和取模运算在二分查找过程中计算对应的row和column索引，时间复杂度为O(log(rows × columns))。

# 整体二分查找，将矩阵视为一维数组
# 时间复杂度: O(log nm) # 对所有元素总数进行二分查找
# 空间复杂度: O(1) # 仅使用固定数量的指针(left, right, mid)，与矩阵大小无关
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 

        # 像处理一维数组一样执行常规二分查找
        while left <= right: # <= 处理left和right指向同一元素但尚未检查的情况
            mid = left + ((right - left) // 2 )
            row = mid // COLUMNS
            col = mid % COLUMNS # 必须用COLUMNS而非ROWS，比如测试用例[[1,1]]用ROWS会导致索引越界

            # 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

        # 未找到目标值
        return False

Neetcode的方法 #

我之后看到Neetcode的解决方案视频，他的思路是先通过二分查找排除不可能包含目标值的行，再在可能的行内对列进行二分查找，时间复杂度标注为O(log(rows) + log(columns))。

# 先对行二分查找，再对列二分查找
# 时间复杂度: O(log n + log m) # 先对行二分，再对列二分
# 空间复杂度: O(1) # 仅使用固定数量的指针(top, bottom, row, left, right)，与矩阵大小无关
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 

        # 这里需要判断循环结束原因：是找到可能的行跳出，还是所有行都被排除
        if top > bottom:
            return False

        # 在目标行内执行二分查找
        left = 0
        right = COLUMNS - 1
        
        while left <= right:
            # 避免其他语言中可能出现的溢出问题
            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

时间复杂度的本质对比 #

根据对数运算的性质log(xy) = log(x) + log(y)，这两种方法的时间复杂度在大O表示法下是完全等价的。大O表示法关注的是渐近复杂度，忽略常数系数和低阶项，而log(rows×columns)和log(rows)+log(columns)在数学上是相等的，所以两种解法的时间效率本质上没有区别。

内容的提问来源于stack exchange，提问作者heretoinfinity