algorithm - 各种版本二分查找的大O

Question

我得到了以下代码，并被告知以大 theta 表示法找到最佳和最差情况下的运行时间。

def find(a, target):
    x = 0
    y = len(a)
    while x < y:
        m = (x+y)/2
        if a[m] < target:
            x = m+1
        elif a[m] > target: 
            y = m
        else:
            return m
    return -1

我知道这段代码在最坏情况下的运行时间是O(lg(n))。但是有人问我，如果第五行从“m=(x+y)/2”改为“m=(2*x+y)/3”，运行时间会改变吗？

我的直觉是运行时间变长了一点，因为它不再像二进制搜索那样将列表切成两半，效率较低，但我不确定此时如何计算大 O

Answer 1

假设在最坏的情况下，我们正在搜索位于 N 个元素的数组中最后的元素。

第一次迭代后，列表应减少到 2N/3。

在第 2 次迭代后，列表应减少到 4N/9

...

在第 (k-1) 次迭代之后，列表应减少到 2 个元素

在第 k 次迭代后，我们最终会找到我们的候选人。

因此 N * (power(2/3,k)) = 1。

k ~ log (N) 以 1.5 为底