python - Python - 嵌套列表中二进制搜索算法的时间复杂度

Question

我有一个嵌套的数字列表，其中有 n 行和列，并且每个数字在每一行和每一列中都在增加。

例如：

A = [[19, 30, 31, 45, 57],
     [25, 32, 32, 51, 69],
     [33, 35, 38, 58, 78],
     [34, 49, 67, 84, 102],
     [44, 54, 73, 90, 115]]

我需要使用二进制搜索来查找一个元素是否在列表中，并且算法最坏情况下的时间复杂度必须为 O(n)。

我有这个代码：

def find(A, v):
    i = 0

    for row in A:
        num = binary_search(v, row, 0, len(row) - 1)
        if num != -1:
            return(i, num)
        i += 1

    return None


def binary_search(v, row, left, right):
    if left > right:
        return -1

    mid = (left + right) // 2

    if row[mid] == v:
        return mid

    elif row[mid] > v:
        return binary_search(v, row, left, mid - 1)

    elif row[mid] < v:
        return binary_search(v, row, mid + 1, right)

我认为这段代码的时间复杂度为 O(n log n)，但我不太确定。那么这段代码的实时复杂度是多少呢？

标签： pythontime-complexitycomplexity-theorybinary-search