Java – super fast autocomplete using binary search in sort files (300000 lines)

In my android app, I want an input field with autocomplete The number of projects is about 300000 The best solution seems to be to put the project into a file (on the SD card), one project per line, with the same number of characters per line, so that I can find a specific line number If the user enters something in the text field, I will binary search (through RandomAccessFile) the file and display suggestions

I hope autocomplete can be super fast (ideally less than 100 milliseconds, but I think it's impossible). What optimization can I do?

Update 1: I will use spaces to convert user input to lowercase English characters (A-Z) Therefore, 'A / B' will be converted to 'a B' and then searched

Uodate 2: I now realize that I need something extra - search for the word start string

Solution

What you're looking for is called trie

http://forums.sun.com/thread.jspa?threadID=5295936

In computer science, trie or prefix tree is an ordered tree data structure used to store key arrays, where the key is usually a string Different from the binary search tree, there is no node in the tree to store the key associated with the node; Instead, its position in the tree shows the key associated with it All descendants of a node have a common prefix to the string associated with the node, and the root is associated with an empty string Values are usually not associated with each node, but only with leaves and some internal nodes corresponding to the key of interest