2 二分查找的主定理如何应用？

Question

为了计算排序数组中数字的出现次数，我使用了两次二分查找

二分查找的递推关系为T(N/2)+1 通过调用它两次，说它是 2T(N/2) +2 是否正确？

但是使用主定理得到的结果是 O(n)，这是错误的

def NbOcc(T,v) :
bg=Bg(T,0,len(T)-1,v) // T(N/2) +1
bd=Bd(T,0,len(T)-1,v) // T(N/2) +1
if bg>bd :
    return 0
else :
    return bd-bg+1

Answer 1

Bg 和 Bd 函数不是 NbOcc 函数的递归调用。因此，NbOcc 函数的时间复杂度为 T(n) = TBG(n-1) + TBD(n-1) + 1，因此 TBG 和 TBD 分别是 Bg 和 Bd 函数的时间复杂度。

现在如果Bg和Bd函数都是二分查找函数，它们的时间复杂度将在O(log(n))。因此，我们可以说 T(n) 在 O(log(n)).

中

总之，您在递归公式中犯了一个错误，因为它们不是递归调用。因此，您不应该使用主定理，因为它不能应用于您的情况（仅适用于分析每个 Bg 和 Bd 函数内部的二进制搜索，具体取决于它们的实现）。