二分查找比较次数的递归关系
Recurrence relation of number of comparisons in binary search
我对二分查找中比较次数的递归关系有疑问。
我在这个网站上看到递归可以写成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 次比较.
请告诉我我是对还是错。
我认为你是对的。
恕我直言，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 比较。不过这里做渐近分析的时候无所谓。
我对二分查找中比较次数的递归关系有疑问。
我在这个网站上看到递归可以写成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 次比较.
请告诉我我是对还是错。
我认为你是对的。
恕我直言，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 比较。不过这里做渐近分析的时候无所谓。