在Java中，对于一个集合来说，是先排序再使用二分查找还是直接使用线性查找更有效？

Question

假设我有一个对象的集合：

List<String> myList = populateMyArrayList();
//Here I am having an ArrayList with 1000 elements

哪种方法更好：

1：归并排序然后二分查找

Collections.sort(myList);
int keyIndex = Collections.binarySearch(myList, key);

2: 顺序查找

for(String s : myList){
   if(s.equals(key)){
      return s;
   }
}

针对需要搜索的集合大小，是否应该有不同的搜索方法？如果是，则如何决定。

编辑1：假设我需要多次搜索列表，并且列表中不会添加新元素。

编辑2：我本可以选择HashSet，但实际上我正在使用List<CustomObject>，并且可以根据CustomObject的不同属性多次搜索List。所以我不能在我的CustomObject中重写equals方法。

- Zeeshan

---

第一种方法将在O(nlogn)时间内运行（由于排序），而线性搜索的时间复杂度为O(n)。 - Alexis C.

线性搜索当然没问题。O(n) vs. O(nlogn + logn) = O(nlogn) - mangusta

我觉得这个问题更适合在 程序员交流社区 提问。 - Ceiling Gecko

你将在列表中搜索多少次？你将插入多少个项目？除非你对这些问题有明确的答案，否则我们给出的任何答案都几乎没有意义。 - SJuan76

@SJuan76 修改了问题，我将会多次搜索该列表，不会添加新的元素。 - Zeeshan

Answer 1

这要看情况而定。

• 如果你只搜索一个字符串，线性搜索更好，因为它的时间复杂度是O(n)
• 如果你需要搜索多个字符串，先排序再使用二分搜索可能更好。它的时间复杂度为O(logn + n*logn)，即O(n*logn)。因此，如果你要检查大约n个字符串，这就更好。
• 如果你只想知道你的集合是否包含一个元素（无序），你应该考虑使用HashSet，它的时间复杂度为O(1)。
• 如果你需要有序的集合并且快速检查包含关系，请使用LinkedHashSet

P.S. 过早优化是万恶之源。

- Absurd-Mind

---

那怎么算是过早了呢？ - Thomas Jungblut

他没有检查一个朴素的解决方案是否满足他的需求。 - Absurd-Mind

值得一提的是，“大O”符号表示算法随着n变化的行为，但并不意味着对于给定的n值，一个算法比另一个算法“更快”。对于给定的n值，一个log(n)算法可能比一个O(n^2)算法慢（如果n足够大，最终具有更好函数的算法将获胜，但这样的n值可能足够大而无意义）。请注意，这些评论不仅适用于您的答案，而且我必须在某个地方发布它们。 - SJuan76

@SJuan76 大O表示假设n趋近于无穷大，因此它对于小的n并没有什么意义。 - Absurd-Mind

这就是我的观点...对于一个有限的值（在本例中为 1000），确定哪种算法“更快”并不那么容易。 - SJuan76

@SJuan76 我并没有提到速度。问题是“哪种方法更有效”，仅仅通过公式的观察，对于一个搜索字符串来说，它是线性搜索。此外，我试图建议OP首先尝试任何方法是否足够（“过早优化...”）。 - Absurd-Mind

Answer 2

如果您只进行一次搜索： 排序+二分搜索的复杂度为O(n * log n)。 线性搜索的复杂度为O(n)。

如果您需要多次搜索，例如k次： 排序+二分搜索的复杂度为O((n + k) * log n)。 线性搜索的复杂度为O(k * n)。

因此，如果您只进行一次搜索，应该选择线性搜索。如果您需要多次搜索，最好先进行排序。 此外，在这种情况下，您可以考虑使用哈希表，其平摊复杂度为O(1)用于元素搜索。

- Andrei Bozantan

---

排序和二分查找的复杂度将是O(nLogn + log n)，而不是O(n * log n)。 - TheLostMind

在复杂性理论中，O(nlog n + log n)被认为等同于O(nlog n)，因为只有最高阶的项被认为是重要的。请查看其他回答，并重新考虑你的负评。 - Andrei Bozantan

如果k >> n，则排序+二分查找的复杂度仅为O(k * log n)，如果k = 1，则复杂度肯定保持为O(n * log n)。我认为适当的复杂度应该是O((k + n)*log n)，或者至少需要一点解释。 - Archeg

@bosonix - 我错了。我以为你把归并排序的复杂度输入为“n”。下次请更清楚明确一些。 - TheLostMind

@AndreiBozantan 为什么是O(n * log n)？假设快速排序（假设这是语言中最常用的排序方式）的复杂度可以忽略不计，那么它的复杂度与二分查找的复杂度相比如何？ - adaba

Answer 3

如果你只搜索一次列表（或很少），那么线性搜索更便宜。如果你更经常地搜索列表，则排序的成本得到回报。排序的成本为O(n log n)平均时间复杂度，然后搜索的是O(log n)。如果你搜索几乎“每个元素”，这也会导致O(n)平均时间复杂度的成本，并且你可以通过排序使其“平衡”。

- Stefan

Answer 4

二分查找的时间复杂度为O(log(m))，比线性查找的O(n)更快。 但是首先必须对数据进行排序：O(n log(n))，这需要更长的时间。

因此，如果数据只填充一次，然后经常搜索，请使用排序和二分查找。 更好的选择是使用Set。而且，HashSet会更好。

- Joop Eggen