I have an array of n strings. I want to select all the elements of the array that starts with the given string.

Sorry if that is not clear. I'll give an example.

input = "as"
array = ["abas", "aras", "as", "ask", "asi", "aso", "atas" ]
output =            ["as", "ask", "asi", "aso"]

Which algorithm will I need to do this selection. I need the fastest algorithm that will perform this operation since I'm using it for autoComplete in JavaScript. So the search should be faster than the typing speed of the user.

Edit: Was just thinking about the data I have to pre-process if using a data structure. The data would be dynamic, and I have to perform insert operation that many number of times. I'm fetching data dynamically using AJAX requests.

Edit 2: The array might contain 1 million entries and the search should be made at two places. One on the server side, to select all elements matching the condition. This can be restricted to 10000 entries, and the other on the client side... search size will be those 10000 entries, and this can be restricted to first 250 entries.

Sorry for the late editing of the question.

  • 1
    Nothing against developing this for fun, but if it's to be used in a production environment I'd recommend checking out some of the existing auto-complete JavaScript libraries such as jQuery
    – l0b0
    Jun 22, 2011 at 11:08
  • I'm developing a library. So I have to code it using pure JavaScript. Searched for pure javascript autocomplete and found that it used the substring function on each element of array that is fetched.. and it was quite slow for faster typing speeds. Jun 22, 2011 at 11:15

3 Answers 3


As a pre-processing step turn your list into a trie.

a trie, also called digital tree or prefix tree, is an ordered tree data structure that is used to store a dynamic set or associative array where the keys are usually strings. Unlike a binary search tree, no node in the tree stores the key associated with that node; instead, its position in the tree defines the key with which it is associated. All the descendants of a node have a common prefix of the string associated with that node, and the root is associated with the empty string. Values are normally not associated with every node, only with leaves and some inner nodes that correspond to keys of interest...

The term trie comes from re-trie-val...


  • edited the question, take a look at the added part. Will trie do good then too. will insertion be like another forming the tree ?? Jun 22, 2011 at 11:12
  • 2
    @Boopathi, building the initial tree is just doing n insertions starting from an empty tree. Each insertion takes O(k) time where k is the length of the string you're inserting. Jun 22, 2011 at 12:18

It's definitely better to use one of the autoComplete algorithms already out there, but if your want to write your own, a trie is the ideal data structure. Insertion and searching both run in constant time i.e O(1), so speed shouldn't be an issue.

Also, this seems similar to what you want: http://webscripts.softpedia.com/script/Forms-and-Controls-C-C/Auto-Complete-Textfield-21580.html


How big is the set of words you want to search through?

For small sets it might be best to simply order your array and then perform a modified binary search to find the first and last matching elements.

For larger sets you probably want to ditch the array altogether and go for a trie.

Given you've updated to say you're expecting a million words (really, a million words? There are only 171,476 words in the Oxford English Dictionary) then a Trie is your best bet. Before you roll your own implementation though, I'd seriously consider some of the freely available autocomplete tools around.

  • the array might contain 1 million entries. Jun 22, 2011 at 11:13
  • hmmm. my array contains proper nouns... names of persons as well as some common nouns Jun 22, 2011 at 11:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.