我听到有人说，由于二分搜索将搜索所需的输入减半，因此它是 log(n) 算法。由于我不是数学背景，我无法与之相关。有人可以更详细地解释一下吗？它是否与对数级数有关？
最佳答案
这是一种更数学的方式来看待它，虽然并不复杂。 IMO 比非正式的更清晰:
问题是，你可以将 N 除以 2 多少次，直到得到 1？这基本上是说，进行二分搜索(一半元素)，直到找到它。在一个公式中，这将是这样的:
乘以 2 倍:
现在做log2:
这意味着您可以将日志划分 N 次，直到将所有内容都划分完毕。这意味着您必须划分 log N(“执行二分搜索步骤”)，直到找到您的元素。
关于algorithm - 如何计算二分查找复杂度，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/8185079/