哪种搜索算法更好？

Question

二分查找算法的大O值为O(log n)，而顺序查找的大O值为O(n)。但在进行二分查找之前，我们需要排序算法，最佳的大O值为O(n.log n)。因此，实际上，二分查找的大O值为O(n.log n)，大于顺序查找的大O值。那么，哪种搜索算法更好呢？

- Victor Mukherjee

Answer 1

实际上取决于搜索的频率。如果您需要搜索数百万次，即使需支付排序的前期成本，也要选择二分查找。这取决于您的使用情况。使用二分查找还可以确保插入操作使列表保持有序，因此它们变得更慢了。

如果您需要执行大量插入操作且仅少量搜索，请考虑使用顺序查找可能会更快。

请注意，直到您处理大量数据时，很多情况甚至都不会被注意到。

- Oleksi

Answer 2

顺序搜索在优化应用程序中很少使用。因为通常更好的方法是找到一个合适的数据结构，然后使用提供频繁搜索的数据结构，时间复杂度为O(n)。

例如，红黑树是一种特殊的平衡二叉树，它提供了插入/删除/搜索所有操作的时间复杂度都为O(log n)。因此，创建、填充和搜索都非常快速。

- oleksii