search - 更喜欢哪种搜索算法？

Question

二分搜索算法的 O 值为 O(log n)，而顺序搜索算法的 O 值为 O(n)。但是我们需要在二进制搜索之前进行排序算法，并且排序算法的最佳大 O 值是 O(n.log n)。因此，实际上，二进制搜索的大 O 值是 O(n.log n)，它大于顺序搜索的 O(n.log n)。那么，哪一个更适合作为搜索算法呢？

Answer 1

在实践中，这取决于您搜索的频率。如果您必须搜索数百万次，则需要二进制搜索，即使您必须支付排序的前期成本。这取决于您的用例。使用二分搜索，您还可以确保插入保持列表排序，因此它们也会变慢。

如果您需要进行大量插入和很少的搜索，顺序搜索可能会更快。

请记住，在您处理大量数据之前，其中很多内容甚至不会被注意到。

Answer 2

顺序搜索实际上很少用于优化的应用程序。因为找到合适的数据结构通常比使用在O(n)中提供常用搜索的数据结构要好得多。

例如，红黑树是一种特殊的平衡二叉树，它在O(log n)内提供插入/删除/搜索。所以创建、填写和搜索都很快。