How to approximate LUT index?

Question

I have an array

...
//a      b
{860,   -30},
{853,   -29},
{846,   -28},
{838,   -27},
{830,   -26},
{822,   -25},
{814,   -24},
...

What is the quickest way using C to find find b with given a value? I guess some approximation is required for that? For example when a = 851 I would like to find -29 as quick as possible.

Answer 1

The fastest general purpose algorithm is a binary search. Depending on the size of the mapping array, you might consider hand-coding the search; that might be plausible for size 32, but I wouldn't go much larger. On a micro-controller, the fully-expanded binary search might be 50% faster, if you're lucky.

But if the mapping is not too non-linear, there's a nice alternative.

Divide the range of a into k equal-sized ranges, where k is not much bigger than the number of entries in the mapping array, such that the mappings of each range endpoint is either the same as or one more than the next range endpoint. (If this is possible; that's precisely what I meant by "not too non-linear"). Create another array which maps each endpoint into an index into the original array. (You only need the indices, not the endpoints, because the endpoints are evenly spaced.) For each range, the bottom endpoint's corresponding index value is the index of the smallest a value in the original array not less than the range's top endpoint. Note that because of the requirement presented above, there can be at most one a value in every range, so the index of each endpoint will always point to the a value for the end of the range, and the a value for the beginning of the range will always be either the same or the previous index.

Now, to look up a value, you first figure out the appropriate range index, which is a simple linear computation ((val - minval)/k) and then compare the value with the indicated a value by looking up the index for the comparison. If the value is less than the looked up a, then subtract one from the index. Then return the b value from the index.

For an example of such an algorithm, see my answer here.