如何计算二分查找复杂度

我听到有人说，由于二分搜索将搜索所需的输入减半，因此它是 log(n) 算法。因为我不是数学背景的，所以我无法理解它。有人可以更详细地解释一下吗？它与对数级数有什么关系吗？

这是一种更数学的方式来看待它，尽管并不复杂。 IMO 比非正式的更清晰：

问题是，你能将 N 除以 2 多少次直到得到 1？这本质上是说，进行二分搜索（一半元素）直到找到它。用公式表示是这样的：

1 = N / 2^x

multiply by 2^x:

2^x = N

now do the log₂:

log₂(2^x)    = log₂ N
x * log₂(2) = log₂ N
x * 1         = log₂ N

这意味着您可以将 log N 次除以，直到将所有内容都除掉。这意味着您必须除以 log N（“执行二分搜索步骤”），直到找到您的元素。