Have you ever interpolated tabled values by hand before? Like a sine table?

Basically your table would have an entry (array element) for each unit of range, possibly 1 per foot or meter. and you would compare your analog input to each entry in turn until you found the first entry bigger than your input. If the first bigger than your input is the first entry (array[0]) then you're out of range as would be the case where your input is bigger than the last entry but in between you can interpolate.

Say your input reads 780 (call it R) and there are table values 740 (call it L) and 800 (call it H).

The percentage of the range between L and H that R falls on is ((100 x (R - L)) / (H - L)). If you want to get 3 places then multiply by 1000 to get 10ths of a percent, etc. Then you have distance corresponding to L plus percentage times 1 unit for your interpolated answer. Just take care about your units if you use integers or use floating-point since exactness isn't really any issue. With FP fastest processing shouldn't be either, it's your choice.