Subj : Re: searching based on 2 keys
To   : comp.programming
From : Christopher Barber
Date : Thu Jun 30 2005 06:53 pm

hungryforc@hotmail.com wrote:
> Hello,
> 
> Suppose I have the following table:
> 
> key    value
> ----   -----
> 
> 2      foo
> 24      bar
> 12     baz
> 
> Now I need an efficient algorithm so that I can search based on either
> the key or the value. One of the solutions is to use 2 tables - but we
> are heavily memory constrained and that is not a solution. Are there
> any other suggestions that I can try?

Assuming the main table is sorted by the key, you just need a second table 
consisting of pointers to the table entries (or array offsets for that matter) 
sorted by the value.  That just takes n * m extra bytes where n is the size
of the table and m is the number of bytes needed to hold the pointer or
offset.  This should just take a fraction of the size of the main table.
Then you can do a binary search on either table.

- Christopher

.