首选哪种搜索算法？

Question

二进制搜索算法具有较大的O(log )值，顺序搜索算法具有较大的O(n)值。但我们需要在二进制搜索之前的排序算法，排序算法的最佳大O值是O(n.log n)。因此，有效地，二分搜索的大O值是O(n.log n)，它比顺序搜索的大O值大。那么，在搜索algo时，哪一个是首选的？

Answer 1

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

如果您需要执行大量插入操作，而很少进行搜索，那么顺序搜索可能会更快。

请记住，在处理大量数据之前，许多数据甚至不会被注意到。

Answer 2

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

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