java - 什么更快 : Using Quicksort then Binary Search OR Just Linear Search?

Question

如果我有一个包含 1000 个元素的整数数组，找到特定元素索引的最快方法是什么？最好先对其进行 QuickSort 然后使用 BinarySearch 还是只使用普通的旧 LinearSearch？

此外，如果我有 100 000 个元素或什至只有 100 个元素，最快的方法会有所不同吗？

谢谢!

Answer 1

线性搜索会更好。线性搜索的 O(N) 的最坏情况小于单独的快速排序(平均 O(nlog n) 但最坏情况 O(N^2)) and 那么您需要添加二进制搜索 (O(log N))。如果您需要多次搜索，排序和使用二分搜索会更好(如果您可以分摊排序成本，那么二分搜索比线性搜索更有效)。