Searching over multiple entries in logn time

I have to write a program which create's an address book that can provide search functionality on multiple fields, with a large number of records. Binary search is an option but the tricky part is that the user can search over any开发者_运维百科 of the four fields (firstName, lastName, phoneNumber, City). So there is no particular column over which I can sort the list. The program should also return search results in logarithmic time. Right now I have created a generic arraylist<contacts> which contains all the four fields. Can anyone suggest what would be the best way to get the search to work in log time.

One approach that is somewhat memory-intensive would be to build four parallel binary search trees (or four Sets whose comparators compare one field at a time). That way, you can do a search on any tree to find a node with a particular field in O(lg n) time.

Use a data base and define the indexes you need.

If you can't use a db, then sort and search. You can sort in O(log n) time on whichever field you need. Then you can search in O(log n) time on the sorted field. Not the way to do it in a production environment, but as an assignment, you can claim, "Total time complexity: O(log n)."

Store it using 4 trees and an arraylist.

The 4 trees should only consider the indices. You shouldn't have to store the whole of each string in the tree, just enough of the string to distinguish it from the rest of the strings (i.e. store characters at the nodes and you get to a leaf when you have enough of a prefix to identify the string(s)). You can be a bit clever by annotating your tree with "skip n letters" nodes so you don't store internal nodes when all strings in that sub-tree are equal on the next n letters.

The arraylist then stores the records.

At the leaves of the trees you just store an index into the arraylist.

If you do this right, you use 350,000 * 2 * 4 (bytes for integer) + X ~= 3MB + X where X is the size of your file, surely your system has that much? You can even leave the data in the file and index into the file.