On Mon, Aug 23, 2010 at 4:45 PM, Patrick Roehl <[email protected]> wrote:
> 3) The binary search from step 1 indicates where the new entry should be > inserted. To add the entry to the list, individual entries are moved one > at a time (to avoid overlapping moves) to open a spot in the list for the > new entry. That's probably going to be an expensive process. Have you considered using a binary tree rather than an array that is kept sorted? Doing a balanced tree is not trivial, but would make searches much faster. If you're not too tight on memory, you could also consider a hash table. You don't want to let the hash table get too full. If the objects are large compared to the index numbers, one would stow the objects in a table as they come, and use a hash table to find them. | Rob
