I want to implement a search filter that is as efficient as possible, that manages book titles in my "library". The search should work as follows:

The user types in the first b letters of the book title. will be returned Number n of book titles that begin exactly with the entered sequence of letters. k is one preset constant that specifies how many book titles should be output. That means if n ≤ k, an alphabetically sorted list of the n book titles is output.

The main problem I'm currently facing is that I don't know what datatype to pick and on what data structure I should implement it because I need it as efficient as possible.

And a follow up question would be, if I use an array for this, I would definitely choose an sorted array right?

Any help is gladly appreciated an I'm NOT asking for an implementation.

CodePudding user response：

This is a very good candidate for a trie. At each keystroke you know exactly how many books start with the prefix. This is a linear operation. So, the search for a prefix of n characters takes O(n) time. In a simple trie implementation, to get the book titles, you would need to traverse the rest of the paths that start with the prefix, but this can also be remedied by having pointers at each node of the trie to the titles that start with that prefix (in other words continue from that node). You could also sort those pointers in advance.

So the whole operation of searching for all the titles that start with a prefix of length n and returning the titles would be O(n m) where m is the number of titles with this prefix.