如果我有一个包含 1000 个元素的整数数组,找到特定元素索引的最快方法是什么?最好先对其进行 QuickSort 然后使用 BinarySearch 还是只使用普通的旧 LinearSearch?
此外,如果我有 100 000 个元素或什至只有 100 个元素,最快的方法会有所不同吗?
谢谢!
最佳答案
线性搜索会更好。线性搜索的 O(N)
的最坏情况小于单独的快速排序(平均 O(nlog n)
但最坏情况 O(N^2)
) and 那么您需要添加二进制搜索 (O(log N)
)。如果您需要多次搜索,排序和使用二分搜索会更好(如果您可以分摊排序成本,那么二分搜索比线性搜索更有效)。
关于java - 什么更快 : Using Quicksort then Binary Search OR Just Linear Search?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/37089589/