Tried a sorted array based search: doesn't work for prefixes. Try a trie.
The trie works. Its much faster too.