哪个更有效,排序,然后在java中的集合或线性搜索上进行二进制搜索

Question

假设我有一个对象集合:

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

哪种方法更好:

1:Mergesort然后二进制搜索

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

2:顺序搜索

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

根据要搜索的集合的大小,搜索方法是否应该有所不同？如果是,那么如何决定.

EDIT1:假设我必须多次搜索列表,并且列表中不会添加任何新元素.

编辑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

PS过早优化是万恶之源.