Searching and lookup tables

Find quickly in a sorted table with binary search, and prepare expensive calculations such as sin or sensor correction as tables in advance.

Binary search

Binary search. Compare with the middle of a sorted table and discard half each time. Even 1000 items take 10 steps.

In a sorted array, compare with the middle value and discard half, again and again. Finding one of 1024 items takes 10 comparisons. It suits sorted correction tables, such as one that finds temperature from thermistor resistance.

Lookup table

Lookup table. Take out a value prepared in advance instead of calculating.

On an MCU without an FPU, sinf() takes hundreds of clocks. Prepare a table that divides one cycle into 256 entries and it is done with a single array read.

static const int16_t sin_lut[256] = { 0, 804, 1608, /* ... */ };
int16_t s = sin_lut[angle >> 8];   // index with the top 8 bits of a 16-bit angle

Add const so it lives in Flash and not in RAM.
If you need values between entries, interpolate linearly between two neighbours.
Generate the table with a Python script and include it as a header file to avoid mistakes.

Where it is used

sin/cos for sinusoidal BLDC drive and FOC
Correcting non-linear sensors such as thermistors and thermocouples
LED gamma correction, motor acceleration profiles

It is the classic trade of memory for speed. Decide the table size together with the precision you need.