Searching for string in sorted list in Java, and possibly all strings beginning with part of string
what would be the most effective way to implement search for a string in sorted list of strings in Java?
And what ab开发者_JS百科out searching for all the string beginning with part of a string?
Thank you for help.
I think you are looking for Collections#binarySearch for both the requirements.
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.
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.
You can just use the Collections.binarySearch().
http://en.wikipedia.org/wiki/Binary_search assuming you are using a java.util.ArrayList
or similar non-linked structure.
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.
精彩评论