查找元素是否存在於未排序數組中的最快方法？

Question

搜索未排序數組以進行單元線性搜索的最快算法是？我的意思是我猜合併排序+二進制搜索的組合會更慢。還有其他選擇嗎？ （根據不涉及多線程的算法）？

Answer 1

是的，如果數組未經排序並且關於其結構的全部知識，那麼搜索元素的最快方法是考慮每個需要線性時間的方法O（n）。

如果您打算搜索數組，那麼您可能需要考慮初始排序，然後將元素插入正確的排序索引（使用二分搜索）。這意味着您的初始排序爲O（n log n），但每個插入和搜索都需要O（log n）。這完全取決於權衡，並且是否優於O（1）插入和O（n）搜索。

你說沒有多線程，但這是一個簡單的方法來提高性能，有多個線程看看列表中的不同塊。