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。

第二次迭代后，列表将减少到 4N/9

. . .

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

在第 k 次迭代之后，我们将最终找到我们的候选者。

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

k ~ log (N) 以 1.5 为底