Gil: 2 section look-up table: two tables, one to look up the MSB, the other the LSB.

Jems: There probably is; However linearizing by formula rarely provides as accurate a result as a look-up table. Give a link to the data sheet of your sensor and someone (maybe me) may have an idea.
It is, in some cases, better to have a look-up table which contains a (possibly negative) correction value, rather than the final result. If, for instance, the correction of a 16 bit value can be held in one byte, this method dramatically reduces table size.
If you, when calculating the look-up table find that the correction amount is the same for ranges of input you can use the following variant which is slower, but takes less space: A look up table build by the following method:
1) All entries are pairs, the first is 'first input value', the second is 'correction value'
2) Take the input value find the matching table entry (compare to 'first input value') by scanning till past, then one step back.
3) Add the (possibly negative) 'correction value'

Have fun,

Erik