Take the 2-minute tour ×

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.

share|improve this question
This is exactly the sort of problem that DBMS are made for. They handle storing the large amounts of data, they handle indexing on multiple fields. And the best thing is, you don't even have to worry about it after setting up your indexes. –  bdares Jun 1 '11 at 3:45

3 Answers 3

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.

share|improve this answer
Some of the files I would be reading contains over 350,000 records. So maintaining 4 parallel trees would eat up all my memory. Is there any other way to do this? –  Jatin Jun 1 '11 at 3:42

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)."

share|improve this answer
This is a project. The only resources I can use are CSV files, to read the data and java collections to store, sort and search. –  Jatin Jun 1 '11 at 3:46
I updated my answer with a non-db approach. P.S. Tagging assignments as "homework" avoids this kind of confusion. :-) –  Ted Hopp Jun 1 '11 at 3:59
:) My professor turned out to be smarter than that. I should have also mentioned that he said we can initialize the list just once. That is, whatever sorting has to be done will have to be done during the initialization phase. Once the user starts searching over any of the records, the program can just do a search. No sorting allowed after initialization. Sorry for the lack of detail in my first post. But do you have any suggestions on how I can approach this problem? –  Jatin Jun 1 '11 at 4:08
Are you restricted to a single list? What other data structures can you use? –  Ted Hopp Jun 1 '11 at 4:16
No other restrictions on what data structures I can use. I have been provided with CSV data files. I can use any kind of structure to hold the data as long as I do the sorting during initialization and the partial string search (begins with...") returns all possible matching values in O(log n) –  Jatin Jun 1 '11 at 4:22

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.

share|improve this answer

Your Answer


