这个特定算法的运行时是什么？

Question

我认为这段代码是(logn)^2，因为每个findindex函数都需要logn深度，我们称之为logn时间？有人能证实这一点吗？我希望你们中的一个能把这当成一个小测验，帮我一下。

给定一个已旋转未知次数的n个整数的排序数组，编写代码在数组中查找一个元素。您可能假设数组最初是按递增顺序排序的。

# Ex
# input find 5 in {15,16,19,20,25,1,3,4,5,7,10,14}
# output 8
# runtime(log n)


def findrotation(a, tgt):
    return findindex(a, 0, len(a)-1, tgt, 0)


def findindex(a, low, high, target, index):
    if low>high:
        return -1

    mid = int((high + low) / 2)

    if a[mid] == target:
        index = index + mid
        return index
    else:
        b = a[low:mid]
        result = findindex(b, 0, len(b)-1, target, index)
        if result == -1:
            index = index + mid + 1
            c = a[mid+1:]
            return findindex(c, 0, len(c)-1, target, index)
        else:
            return result

Answer 1

这个算法应该是o(logn)，但从实现的角度来看不是。

>

在您的算法中，您不是只选择左子数组还是右子数组，而是尝试使用这两个子数组，即O(N)。

您正在对数组A[LOW:mid]和A[mid+1:]进行切片，后者是O(n)。

这使得您的总体复杂性在最坏的情况下O(n^2)。

假设数组中没有重复项，Python3中o(logn)二进制搜索的理想实现如下所示-

A=[15,16,19,20,25,1,3,4,5,7,10,14]
low = 0
hi = len(A) - 1


def findindex(A, low, hi, target):
    if low > hi:
        return -1
    mid = round((hi + low) / 2.0)
    if A[mid] == target:
        return mid
    if A[mid] >= A[low]:
        if target < A[mid] and target >= A[low]:
            return findindex(A, low, mid - 1, target)
        else : 
            return findindex(A, mid + 1, hi, target)

    if A[mid] < A[low]:
        if target < A[mid] or target >= A[low]:
            return findindex(A, low, mid - 1, target)
        else :
            return findindex(A, mid + 1, hi, target)

    return -1

print(findindex(A, low, hi, 3))