Well, in C I would keep the array with structures (string + integer) and then add 2 more arrays with integer offsets into array with structures. The latter 2 arrays are sorted appropriately. Then lookup speed is O(logN).
The above approach is simple, saves space and still provides descent speed for lookups in both directions. One can also use random records instead of array with all records, but then "indexes" maybe be larger on 64-bit systems since addresses are 8 bytes and offsets can be kept 4 bytes.