what would be the most effective way to implement search for a string in sorted list of strings in Java?
And what about searching for all the string beginning with part of a string?
Thank you for help.
Add a comment
|
6 Answers
I think you are looking for Collections#binarySearch for both the requirements.
2 Comments
amit
since List doesn't guarantee random access ("it takes the same time to access each element") , using binary search on a list might be very inefficient, for LinkedList, it will take O(nlogn) while the "banal" solution will be O(n).
Voo
@amit The java collections framework is intelligent enough to distinguish between random access lists and others, so you'll get O(log n) comparisons and O(n) field accesses.
A list really isn't the right datastructure for this. First of all binarySearch will in the best case do O(N) for a linkedList - since a list doesn't support random access you don't gain anything by having it sorted.
What you're looking for is a trie. The wiki page describes the advantages and how it works good enough for me not to waste my time trying to trump it. While it doesn't describe the advantages over a sorted LinkedList, just remember that inserting into a sorted LinkedList is O(N) link traversals and O(log n) element comparisons, as is finding an object. The trie is more efficient and still supports all operations you would get from a sorted linked list.
Google finds several results for libraries that support that structure like this one but I haven't used any of them. A trie is still a quite simple data structure (compared to eg AVL trees) so you could implement it yourself quite easily though.
Comments
To search for non-beginning strings (i.e. 'and' matches 'andrew', 'candy' and 'sand') you will have to do brute force.
For beginning of string, use a BST.
Comments
You can just use the Collections.binarySearch().
Comments
http://en.wikipedia.org/wiki/Binary_search assuming you are using a java.util.ArrayList or similar non-linked structure.
8 Comments
amit
binary search is useless for a list, it doesn't have random access to its elements.
Etienne de Martel
@amit Depends, in Java "list" generally refers to the
List interface and its implementations, which actually has random access.amit
@Ethan, @Etienne: what I meant was: List doesn't guarantee random access. random access is defined as "it takes the same time to access each element". for instance, LinkedList - which is implementing LinkedList, will take O(nlogn) time on binary search, because every access is O(n)
JustinKSU
My assumption is that he is using an ArrayList.
Ethan Cabiac
We agree that the performance of search algorithms vary greatly on the actual implementation of the underlying structure. If the underlying list is not Random access, then the only answer to this problem is Brute force. I think every one else made the assumption that the underlying data structure was one that provided O(1) in order for the question to make any sense.
|
uther.lightbringer rote:
what would be the most effective way to implement search for a string in sorted list of strings in Java?
As other already mentioned, you can use Collections.binarySearch(...) for that. Make sure your list is sorted: otherwise you'll most likely not get the right results.
uther.lightbringer rote:
And what about searching for all the string beginning with part of a string?
Either loop through the list from start to finish and check each word, or create (or grab from the net) a radix tree which can find the words starting with a certain (sub) string much faster than looping over the list of words.
Comments
