java - 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>我可以搜索List根据 CustomObject 的不同属性多次。所以我不能覆盖 equals我的 CustomObject 中的方法

Answer 1

这取决于。

• 如果您只搜索一个字符串，线性搜索会更好，因为它的时间复杂度为 O(n)
• 如果您要搜索多个字符串，请先排序，然后进行二进制搜索可能会更好。它将是O(logn + n*logn)，即O(n*logn)。因此，如果您正在检查 ca。 n 个字符串，这个更好。
• 如果您只想知道 Collection 是否包含元素(忽略顺序)，则应考虑使用 HashSet，其时间复杂度为 O(1)。
• 如果您需要顺序和快速包含方法，请使用LinkedHashSet

附注过早的优化是万恶之源。