algorithm - 二分查找比较次数的递归关系

Question

我对二分查找中比较次数的递归关系有疑问。

我在这个网站上读到递归可以写成 T(n) = T(n/2) + 1 http://faculty.simpson.edu/lydia.sinapova/www/cmsc250/LN250_Weiss/L14-RecRel.htm

根据我的说法，它应该是 T(n) = T(n/2) + 2，因为在最坏的情况下，该元素可能不存在于数组中，我们最终会在每次传递中进行 2 次比较。

请告诉我我是对还是错。

Answer 1

我认为你是对的。

恕我直言，compare a b意味着我们知道 a=b , a>b或 a<b同时。也就是说，1次比较可能有3种不同的结果。

但是对于编程语言。我们必须使用 2 个比较。

if mid == x:      found it!          # 1st
else if mid < x:  search right       # 2nd
else:             search left

你的意思是 ==和 <是2个比较。

但不影响结果。因为我们使用大 O 表示法来表示复杂性。这只是一个常数问题，但是O通常不关心它。

根据 master theorem . +1或 +2将导致相同的复杂性 O(log n) .

我们想要的通常是一个极限(Big-O)，而不是数学方程式的精确结果。

我认为这里重要的是 1和 2都是常数时间。我们也可以拆分== , >进入机器指令，它可能大于2 .或者也许某些编程语言或 CPU 利用比较，它只花费 1比较。但是这里在做渐近分析的时候无所谓。

---

1. https://en.wikipedia.org/wiki/Master_theorem
2. https://en.wikipedia.org/wiki/Asymptotic_analysis