查找元素是否存在于未排序数组中的最快方法？

Question

搜索未排序数组以进行单元线性搜索的最快算法是？我的意思是我猜合并排序+二进制搜索的组合会更慢。还有其他选择吗？ （根据不涉及多线程的算法）？

Answer 1

是的，如果数组未经排序并且关于其结构的全部知识，那么搜索元素的最快方法是考虑每个需要线性时间的方法O（n）。

如果您打算搜索数组，那么您可能需要考虑初始排序，然后将元素插入正确的排序索引（使用二分搜索）。这意味着您的初始排序为O（n log n），但每个插入和搜索都需要O（log n）。这完全取决于权衡，并且是否优于O（1）插入和O（n）搜索。

你说没有多线程，但这是一个简单的方法来提高性能，有多个线程看看列表中的不同块。