二分搜索是 O(log n) 还是 O(n log n)？

Question

我遇到过 O(log n) 和 O(n log n) 的时候。这也是一个非常受欢迎的面试问题。所以当面试官盲目地问你二分搜索的运行时间是多少（没有上下文）？你应该说什么？

Answer 1

听起来像是一个技巧问题，因为没有上下文。看起来面试官想要涵盖二进制搜索好的情况和不好的情况。

因此，当您对元素列表进行排序并搜索单个元素时，二分搜索非常有用，在这种情况下，它的成本为O(logn).

现在，如果我们没有排序的数组，排序的成本是O(n logn)，然后您可以应用第一种情况。在这种情况下，最好将值放在 set 或 map 中然后搜索（执行时间将O(n)用于插入，O(1)用于搜索）。

这两种情况都依赖于单一搜索。二分搜索不是用于在单次执行中搜索 n 个元素（或任何数量的元素取决于n，例如n/2元素，n/4甚至logn元素 - 对于固定数量的它可以）。对于这种情况，有更好的方法（集合和映射）。

Answer 2

O(log n)，平均情况和最坏情况。从来没有听说过有人声称它是 O(n log n)。