Hi,

use an array to keep the values, create a B-Tree to do the search. However instead of the values keey in the tree-nodes the index of the array elements you search for.

The hardest thing here is to keep the array in sync with the tree.

Basically it is something like an indexed array.

update: Uaaa, I missed the line with "never more than 1000 elements". Then my proposal is a total overkill. Isn't there a chapter in PBP about benchmarking?