Which is more efficient, Sorting and then Binary Search over a Collection or Linear Search in java
binary-search, collections, java, linear-search, mergesort
Solution
It depends.
- If you are searching for only one string the linear search is better because it is in `O(n)`
- If you are searching for multiple strings first sorting and then binary searching maybe better. it will be `O(logn + n*logn)` which is `O(n*logn)`. So if you are checking for ca. `n` strings, this one is better.
- If you only want to know if your Collection contains an element (ignoring order), you should consider using `HashSet` which has `O(1)`.
- If you need order and a fast contains method, use `LinkedHashSet`
P.S. premature optimization is the root of all evil.
Problem
Suppose I am having a Collection of object: ``` List<String> myList = populateMyArrayList(); //Here I am having an ArrayList with 1000 elements ``` Which is the better approach: 1 : Mergesort then Binary Search ``` Collections.sort(myList); int keyIndex = Collections.binarySearch(myList, key); ``` 2 : Sequential Search ``` for(String s : myList){ if(s.equals(key)){ return s; } } ``` Should there be a difference in searching approach based on the size of the collection to be searched? If YES then how to decide. EDIT1: Suppose I have to search the list a couple of times, and no new elements will be added in the list. EDIT2: I could have gone for a `HashSet`, but I am actually having a `List<CustomObject>` and I can search the `List` multiple times based on different attributes of CustomObject. So I can't have a overridden `equals` method in my CustomObject