问题描述
我听到有人说，由于二分搜索将搜索所需的输入减半，因此它是 log(n) 算法.由于我不是数学背景，我无法与之相关.有人可以更详细地解释一下吗?和对数级数有关系吗?
I heard somebody say that since binary search halves the input required to search hence it is log(n) algorithm. Since I am not from a mathematics background I am not able to relate to it. Can somebody explain it in a little more detail? Does it have to do something with the logarithmic series?
推荐答案
这里有一种更数学的方式来看待它，虽然并不复杂.IMO 比非正式的要清楚得多:
Here a more mathematical way of seeing it, though not really complicated. IMO much clearer as informal ones:
问题是，你可以将 N 除以 2 多少次，直到得到 1?这基本上是说，进行二分搜索(一半元素)，直到找到它.在一个公式中，这将是这样的:
The question is, how many times can you divide N by 2 until you have 1? This is essentially saying, do a binary search (half the elements) until you found it. In a formula this would be this:
1 = N/2
乘以2:
2 = N
现在做日志:
log(2) = log N
x * log(2) = log N
x * 1 = log N
这意味着您可以将日志划分 N 次，直到将所有内容都划分完毕.这意味着您必须对 log N 进行除法(执行二分搜索步骤")，直到找到您的元素.
this means you can divide log N times until you have everything divided. Which means you have to divide log N ("do the binary search step") until you found your element.
这篇关于如何计算二分查找复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！