Search & Lookup

Search, lookup tables, hashing, and dispatch

Use sorted arrays and binary search when data changes rarely and deterministic logarithmic lookup matters. Use direct indexing or bitmaps for small dense key spaces. Use bounded open addressing when average constant-time lookup justifies fixed table memory and explicit full-table behavior.

Binary search is an invariant over a half-open interval [lo,hi). For lower_bound, every index before lo is known too small and every index at or after hi is known large enough. The midpoint lo+(hi-lo)/2 avoids overflow and termination follows because each branch strictly shrinks the interval.

A hash table needs more design than a hash function: capacity, load factor, collision policy, empty/tombstone representation, duplicate semantics, probe termination, and denial-of-service bounds. In hard real-time paths, worst-case linear probing can be unacceptable even if average lookup is O(1).

Static command tables are often better than general maps. Sort at build time, binary-search string views without copying, and store function pointers or IDs in flash. A perfect hash or trie becomes worthwhile only when measured requirements justify its additional generator or node storage.

Patterns and when they apply

lower_bound

Calibration brackets, timestamp ranges, sorted command tables. Cost: O(log n), no allocation. Avoid when: Mixing closed and half-open interval formulas.

direct table/bitmap

Dense IDs, resource slots, ready priorities. Cost: Memory proportional to key space. Avoid when: Sparse huge keys.

open addressing

Bounded fixed map with good average lookup. Cost: Performance collapses near full. Avoid when: No probe bound or missing full-table status.

Calibration lower bound

1. Start lo=0 and hi=n.
2. Probe the overflow-safe midpoint.
3. If table[mid]<query, exclude mid and everything before it.
4. Otherwise keep mid as a candidate by setting hi=mid.

lo ends at the first entry not less than the query, including n when none exists.

Checklist

• Is the table sorted under the exact comparator?
• What is returned when no key matches?
• Can duplicate keys exist?
• How full may the hash table become?
• Is worst-case lookup bounded enough?

Easy - Calibration Table Lower Bound

Every calibration table on a device: thermocouple linearisation, sensor compensation curves, gamma tables - find the bracketing entry for a measured value.

Return the first calibration entry whose raw code is not less than the query. Avoid midpoint overflow and handle an empty table.

Calibration-table lower bound

Returns the first index i with table[i]>=query, or n when none exists. An empty table may use NULL.

#include <stddef.h>
#include <stdint.h>

size_t lower_bound_u16(const uint16_t *table, size_t n,
                       uint16_t query) {
    size_t lo = 0u;
    size_t hi = n;
    while (lo < hi) {
        size_t mid = lo + (hi - lo) / 2u;
        if (table[mid] < query) {
            lo = mid + 1u;
        } else {
            hi = mid;
        }
    }
    return lo;
}

• The active range is half-open [lo,hi).
• Everything before lo is too small; everything at or after hi is a candidate.
• lo+(hi-lo)/2 avoids lo+hi overflow and every branch shrinks the range.

Cases the tests must cover

• empty table
• query before first and after last
• exact first/last match
• duplicate values return first
• single element

How it gets written wrong

• Caller must supply a sorted table.
• Do not dereference table when n is zero.

Medium - Piecewise Linear Calibration

Converting a raw ADC count to a physical unit through a piecewise-linear calibration curve, which is how nearly every non-linear sensor is linearised in firmware.

Find the two surrounding calibration points with binary search and interpolate the engineering value using overflow-safe fixed-point arithmetic.

Binary-search calibration with fixed-point lerp

Finds the bracketing points around raw in a table sorted by raw code, interpolates linearly in overflow-safe fixed point, and writes the engineering value to *value. Returns false below/above the table range, for n<2, or NULL arguments.

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

typedef struct { uint16_t raw; int32_t eng; } point_t;

bool calibrate(const point_t *table, size_t n, uint16_t raw, int32_t *value) {
    if (table == NULL || value == NULL || n < 2u) return false;
    if (raw < table[0].raw || raw > table[n - 1u].raw) return false;

    /* Lower bound: first index whose raw code is >= the query. */
    size_t lo = 0u, hi = n;
    while (lo < hi) {
        size_t mid = lo + (hi - lo) / 2u;   /* overflow-safe midpoint */
        if (table[mid].raw < raw) lo = mid + 1u; else hi = mid;
    }
    if (table[lo].raw == raw) {             /* exact calibration point */
        *value = table[lo].eng;
        return true;
    }
    /* Bracketing pair is [lo-1, lo]. Interpolate in 64-bit so the
       (eng span) x (raw offset) product cannot wrap. */
    const point_t *a = &table[lo - 1u];
    const point_t *b = &table[lo];
    int64_t num = (int64_t)(b->eng - a->eng) * (int64_t)(raw - a->raw);
    int64_t den = (int64_t)(b->raw - a->raw);
    *value = a->eng + (int32_t)(num / den);
    return true;
}

• A calibration table is just a piecewise-linear function. Two steps solve it: binary search finds the segment, then a linear interpolation (lerp) estimates the value inside it.
• The midpoint is computed as lo + (hi - lo)/2 — the textbook fix for the (lo + hi)/2 overflow bug that lived in the JDK's binary search for nine years.
• An exact table hit short-circuits the lerp, which also avoids the divide-by-zero that a zero-width segment (duplicate raw codes) would cause — validate your tables at build time so segments always have width.
• The multiply is done in int64_t: eng spans of ±100000 times raw offsets up to 65535 need about 34 bits. Widening before multiplying is cheap on any 32-bit core with a 32x32→64 multiply.
• Extrapolation is refused outright; outside the calibrated range a sensor reading is meaningless, and returning false forces the caller into its fault path.

Cases the tests must cover

• Query exactly on a point returns its eng value bit-exact
• Midpoint of a linear table returns the arithmetic mean of neighbors
• raw below table[0] and above table[n-1] both return false
• Non-linear table interpolates within the correct segment only
• Negative eng spans (decreasing output) interpolate with correct sign

How it gets written wrong

• Interpolating with 32-bit products — the classic silent-wrap bug that only appears with hot sensors.
• Dividing before multiplying (eng_span / raw_span * offset) loses all fractional precision in integer math.
• Accepting n == 1 and reading table[lo-1] out of bounds.
• Using floating point on an M0/M0+ where every float op is a library call; this fixed-point form is integer-only.

Medium - Search a Rotated Log Index

Searching a circular log by timestamp when the log has wrapped, so the array is sorted but starts in the middle.

A sorted sequence-number index was rotated after flash compaction. Find a target without restoring the array.

Binary search in a rotated sequence index

Returns the index of target in a strictly increasing sequence that was rotated at an unknown pivot, or -1 when absent. No restoration copy is made.

#include <stddef.h>
#include <stdint.h>

ptrdiff_t rotated_find(const uint32_t *seq, size_t n, uint32_t target) {
    if (seq == NULL || n == 0u) return -1;
    size_t lo = 0u, hi = n - 1u;
    while (lo <= hi) {
        size_t mid = lo + (hi - lo) / 2u;
        if (seq[mid] == target) return (ptrdiff_t)mid;
        /* At least one half is always sorted; find which one. */
        if (seq[lo] <= seq[mid]) {
            /* Left half sorted: is target inside its known range? */
            if (seq[lo] <= target && target < seq[mid]) hi = mid - 1u;
            else lo = mid + 1u;
        } else {
            /* Right half sorted. */
            if (seq[mid] < target && target <= seq[hi]) lo = mid + 1u;
            else hi = mid - 1u;
        }
    }
    return -1;
}

• Flash compaction can rotate a log index so it looks like [40,50,60,10,20,30]. The rescue fact: whatever pivot you pick, one of the two halves is still perfectly sorted.
• Each iteration identifies the sorted half and asks a question you can answer in O(1): does the target lie between its endpoints? If yes, search that half; if no, the target can only be in the other half.
• The seq[lo] <= seq[mid] test decides which half is sorted. Equality happens only when lo == mid, which is handled because the target check already ran.
• This stays O(log n) and touches only the stored data — important when the index lives in flash and copying it to RAM for re-sorting costs a page of wear and a pile of cycles.

Cases the tests must cover

• [40,50,60,10,20,30] find 20 → index 4
• Rotation by 0 (plain sorted) still finds every element
• Rotation by n-1 (maximally rotated) finds first and last
• Absent target returns -1
• n = 1 hit and miss both correct

How it gets written wrong

• Using strict < on the seq[lo] <= seq[mid] test — the two-element case [2,1] misclassifies the sorted half.
• Searching the sorted half without the range check first; 'sorted' alone does not say the target is in it.
• Finding the pivot first, then searching: two binary searches where one interleaved pass does the job.

Easy - Command Table Lookup

Dispatching a received command string to a handler: AT commands, a debug shell, a Modbus function code, a CAN message id.

Search a sorted table of command-name/function-pointer pairs without copying strings. Return NULL for an unknown command.

Binary search over a sorted command table

Returns the handler for name from a table sorted by name (strcmp order), or NULL when unknown. No string copies; comparisons run against the stored const strings.

#include <stdbool.h>
#include <stddef.h>
#include <string.h>

typedef void (*command_fn)(void);
typedef struct { const char *name; command_fn fn; } command_t;

command_fn find_command(const command_t *table, size_t n, const char *name) {
    if (table == NULL || name == NULL) return NULL;
    size_t lo = 0u, hi = n;
    while (lo < hi) {
        size_t mid = lo + (hi - lo) / 2u;
        int cmp = strcmp(name, table[mid].name);
        if (cmp == 0) return table[mid].fn;
        if (cmp < 0) hi = mid; else lo = mid + 1u;
    }
    return NULL;
}

• Function-pointer dispatch tables beat switch statements once command counts grow: the compiler cannot binary-search a switch on strings, but a sorted table gives O(log n) dispatch in ROM.
• strcmp(name, table[mid].name) compares the query against the stored entry; the sign of the result drives the same lo/hi halving as numeric search. Each probe costs one string compare of at most m bytes, hence O(log n · m).
• Nothing is copied — the query string and the table strings are only read. That keeps the function safe to call with a received UART line still sitting in the DMA buffer.
• The table must be sorted by the same ordering strcmp uses; a build-time static_assert script or unit test over the table is the usual guard.

Cases the tests must cover

• First, middle, and last commands all resolve to their handlers
• Unknown name returns NULL
• Name that is a prefix of a stored command returns NULL (no partial match)
• Empty table returns NULL
• Case mismatch ("LED" vs "led") returns NULL — strcmp is case-sensitive

How it gets written wrong

• Storing the table unsorted and relying on binary search anyway — order is the entire precondition.
• Comparing with strncmp(name, entry, strlen(name)) accidentally enables prefix matches.
• Linear if/else chains of strcmp: fine for 5 commands, a latency cliff for 50.

Hard - Unique Command Prefix

A debug console that accepts unambiguous abbreviations, the way most CLIs let you type 'res' for 'reset' but reject it if 'restore' also exists.

Given a sorted command table and an input prefix, return the command only when exactly one entry matches; otherwise report none or ambiguous.

Unambiguous prefix dispatch via lower/upper bounds

Returns MATCH_ONE with the handler when exactly one stored command starts with prefix, MATCH_NONE when no entry matches, and MATCH_AMBIGUOUS when several do. Empty prefix is ambiguous unless the table is empty.

#include <stdbool.h>
#include <stddef.h>
#include <string.h>

typedef void (*command_fn)(void);
typedef struct { const char *name; command_fn fn; } command_t;
typedef enum { MATCH_NONE, MATCH_ONE, MATCH_AMBIGUOUS } match_kind_t;
typedef struct { match_kind_t kind; command_fn fn; } match_t;

static bool starts_with(const char *s, const char *prefix) {
    while (*prefix != '\0') {
        if (*s != *prefix) return false;
        s++;
        prefix++;
    }
    return true;
}

match_t match_prefix(const command_t *table, size_t n, const char *prefix) {
    match_t none = { MATCH_NONE, NULL };
    if (table == NULL || prefix == NULL || n == 0u) return none;
    /* Sorted table => every match is one contiguous run. Lower-bound the
       first possible start, then test the one or two candidates. */
    size_t plen = strlen(prefix);
    size_t lo = 0u, hi = n;
    while (lo < hi) {
        size_t mid = lo + (hi - lo) / 2u;
        if (strncmp(table[mid].name, prefix, plen) < 0) lo = mid + 1u;
        else hi = mid;
    }
    if (lo == n || !starts_with(table[lo].name, prefix)) return none;
    if (lo + 1u < n && starts_with(table[lo + 1u].name, prefix)) {
        match_t amb = { MATCH_AMBIGUOUS, NULL };
        return amb;
    }
    match_t one = { MATCH_ONE, table[lo].fn };
    return one;
}

• In a sorted table, all strings sharing a prefix sit in one contiguous block. So you only need to find where that block starts (a lower-bound binary search) and check whether the block has one entry or more.
• strncmp against the prefix with the prefix length acts like comparing against an infinitely padded string: 'st' sorts before 'status' but after 'reset', exactly placing the search at the first candidate.
• After the search, lo is the first entry that could match. Verifying with starts_with rejects the case where lo points just past the prefix block (no match at all).
• Only the first two candidates are ever inspected — a third match cannot exist without a second — which is how the search stays O(log n + k) with k the prefix length.
• Returning an explicit AMBIGUOUS kind instead of NULL lets the shell print 'did you mean: start, status?' instead of a bare error.

Cases the tests must cover

• Prefix matching exactly one command returns MATCH_ONE and its handler
• Prefix shared by two commands returns MATCH_AMBIGUOUS
• Full command name still returns MATCH_ONE (a string is its own prefix)
• Prefix beyond the alphabetically last entry returns MATCH_NONE
• Empty prefix over a non-empty table returns MATCH_AMBIGUOUS

How it gets written wrong

• Linearly scanning and counting matches — O(n) where O(log n + k) was required.
• Returning the first match without checking for a second; silent ambiguity executes the wrong handler.
• strncmp without then verifying starts_with: strncmp(a,b,plen)==0 already proves the match, but using only the bound without the check misfires when plen is 0.

Easy - First and Last Timestamp

Extracting every log entry inside a time window from a sorted event log, which is the core query of any on-device diagnostic dump.

In a sorted tick log containing duplicates, find the first and last index of a requested tick using logarithmic search.

First/last index of a duplicate timestamp

Returns {first,last} inclusive indices of target in a sorted tick log, or {n,n} when absent. Both halves run in logarithmic time.

#include <stddef.h>
#include <stdint.h>

typedef struct { size_t first; size_t last; } index_range_t;

index_range_t equal_range_u32(const uint32_t *ticks, size_t n, uint32_t target) {
    index_range_t miss = { n, n };
    if (ticks == NULL || n == 0u) return miss;
    /* Lower bound: first index with ticks[i] >= target. */
    size_t lo = 0u, hi = n;
    while (lo < hi) {
        size_t mid = lo + (hi - lo) / 2u;
        if (ticks[mid] < target) lo = mid + 1u; else hi = mid;
    }
    if (lo == n || ticks[lo] != target) return miss;
    /* Upper bound: first index with ticks[i] > target. */
    size_t lo2 = lo, hi2 = n;
    while (lo2 < hi2) {
        size_t mid = lo2 + (hi2 - lo2) / 2u;
        if (ticks[mid] <= target) lo2 = mid + 1u; else hi2 = mid;
    }
    index_range_t hit = { lo, lo2 - 1u };
    return hit;
}

• Equal range = lower bound plus upper bound. The lower bound lands on the first occurrence; the upper bound lands one past the last, so last = upper - 1.
• The two searches differ by a single comparison: '<' for lower bound vs '<=' for upper bound. Memorize the pair and you never hand-roll duplicate handling again.
• Returning {n,n} for a miss mirrors C++ equal_range semantics and cannot be confused with a real hit, because a hit always has first <= last < n.
• Both halves are plain binary search, so the whole query stays O(log n) even when the log is one long run of identical ticks.

Cases the tests must cover

• [1,2,2,2,5] target 2 → {1,3}
• Target appearing once → {i,i}
• All elements equal to target → {0, n-1}
• Absent target between two values → {n,n}
• Target larger than everything → {n,n}

How it gets written wrong

• Finding any occurrence with one binary search then scanning linearly outward — O(n) in the all-duplicates worst case.
• Forgetting the ticks[lo] != target check: the lower bound of an absent target points at its insertion slot, not a match.
• Returning upper as last instead of upper - 1, an off-by-one that reads one element past the run.

Easy - Integer Square Root

RMS current calculation, vector magnitude from accelerometer axes, distance from a time-of-flight sensor - anywhere a magnitude is needed without a float unit.

Return floor(sqrt(n)) for a uint32_t without floating point, overflow, library math calls, or a linear scan.

Integer square root by binary search

Returns floor(sqrt(n)) for any uint32_t. Pure integer arithmetic, no libm, no float, no linear scan.

#include <stdint.h>

uint16_t isqrt_u32(uint32_t n) {
    /* Answer lives in [0, 65535]; 65536^2 would exceed uint32_t. */
    uint32_t lo = 0u, hi = 65536u;   /* hi is exclusive: hi*hi never computed on 32 bits */
    while (hi - lo > 1u) {
        uint32_t mid = lo + (hi - lo) / 2u;
        /* mid <= 65535 so mid*mid <= 0xFFFE0001, which fits uint32_t. */
        if (mid * mid <= n) lo = mid; else hi = mid;
    }
    return (uint16_t)lo;             /* lo*lo <= n < (lo+1)*(lo+1) */
}

• sqrt is monotonic, so 'is mid*mid <= n?' is a yes/no question that binary search answers in 16 iterations for the whole 32-bit range — no floats, no sqrtf, no libm pull-in.
• The interval is half-open [lo, hi): lo is always a value whose square fits, hi always one whose square is too big. When they are adjacent, lo is the floor of the root.
• Bounding hi at 65536 keeps mid <= 65535, and 65535^2 = 4294836225 still fits in uint32_t — so mid*mid can never overflow, which is the usual isqrt bug.
• The invariant lo^2 <= n < hi^2 holds on every iteration; stating it before writing the loop is what makes the edge cases (0, 1, UINT32_MAX) fall out correctly.

Cases the tests must cover

• isqrt_u32(0) = 0, isqrt_u32(1) = 1
• isqrt_u32(0xFFFFFFFFu) = 65535
• Perfect squares: isqrt_u32(65535u*65535u) = 65535
• One below a square: isqrt_u32(k*k - 1) = k - 1
• Monotonicity: isqrt(a) <= isqrt(b) whenever a <= b across random pairs

How it gets written wrong

• Squaring mid up to 65536 in uint32_t wraps and flips the comparison.
• Using (lo + hi) / 2 with signed int — overflow on large ranges.
• Newton's method starting at n: correct but needs a division per step and careful convergence handling for 0.

Hard - Kth Sample from Two Sorted Streams

Merging two sorted sensor streams to find a percentile without materialising the merged array - median of two channels, combined-stream statistics.

Find the kth smallest value across two sorted sample arrays without merging them. Either array may be empty.

Kth across two sorted streams by partition search

Writes the kth smallest value (0-based k < na+nb) across two sorted arrays into *out without merging. Returns false for NULL out or k out of range. Either array may be empty.

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

bool kth_two_sorted(const int16_t *a, size_t na,
                    const int16_t *b, size_t nb,
                    size_t k, int16_t *out) {
    if (out == NULL || k >= na + nb) return false;
    if (a == NULL) na = 0u;
    if (b == NULL) nb = 0u;
    /* Binary search how many of the first k elements come from a. */
    size_t lo = k > nb ? k - nb : 0u;      /* must take at least k-nb from a */
    size_t hi = k < na ? k : na;           /* can take at most min(k,na) */
    while (lo <= hi) {
        size_t i = lo + (hi - lo) / 2u;    /* taken from a */
        size_t j = k - i;                  /* taken from b */
        int32_t aL = i ? a[i - 1u] : INT16_MIN - 1;
        int32_t bL = j ? b[j - 1u] : INT16_MIN - 1;
        int32_t aR = i < na ? a[i] : INT16_MAX + 1;
        int32_t bR = j < nb ? b[j] : INT16_MAX + 1;
        if (aL > bR) { hi = i - 1u; }          /* took too many from a */
        else if (bL > aR) { lo = i + 1u; }     /* took too few from a */
        else {
            *out = (int16_t)(aL > bL ? aL : bL);
            return true;
        }
        if (hi == (size_t)-1) break;           /* lo==0,hi wrapped: impossible here */
    }
    return false;   /* unreachable for valid sorted inputs */
}

• The kth smallest element is defined by a partition: take i elements from a and k-i from b such that everything taken is <= everything not taken. Searching for the right i is a binary search over count, not value — that is where O(log min(na,nb)) comes from.
• The partition is correct when a[i-1] <= b[k-i] and b[k-i-1] <= a[i]: the taken left sides never overtake the untaken right sides. If a's last taken value beats b's first untaken one, we took too many from a; otherwise too few.
• Empty-side sentinels (wider than int16_t so real extremes never compare equal to them) let one code path handle i==0, i==na, and empty arrays without special cases.
• The lo bound k-nb handles the case where b alone cannot supply k elements; the hi bound min(k,na) handles a being short. Clamping the search range first is what guarantees j stays inside b.

Cases the tests must cover

• a=[1,3], b=[2,4], k=0..3 → 1,2,3,4 in order
• a empty → kth element of b; b empty → kth of a
• All of a smaller than all of b: k < na indexes a, else b[k-na]
• Duplicates across arrays return the correct duplicated value
• k = na+nb-1 returns the global maximum

How it gets written wrong

• Merging into a scratch buffer: simple, but violates the no-merge contract and costs O(n) memory traffic.
• Using int16_t sentinels for the virtual edges — a real INT16_MIN in the data then collides with the sentinel.
• Unclamped search range lets j = k - i index past the end of b.

Medium - Pair with Target Delta

Finding a pair of samples whose difference matches a signature - detecting a specific transition in a captured waveform, or matching a request to a response id.

Find two sensor values that sum to a target using a caller-provided fixed open-addressing table. Define duplicate-key and full-table behavior.

Pair with target sum via caller-owned open addressing

Finds two values (distinct indices) summing to target. Uses a caller-provided, all-EMPTY-initialized table of cap slots (cap power of two, cap >= 2*n recommended). Returns false when no pair exists or the table fills. Duplicate values pair only when present twice.

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

typedef enum { SLOT_EMPTY, SLOT_USED } slot_state_t;
typedef struct { slot_state_t state; int16_t value; size_t index; } hash_slot_t;
typedef struct { size_t first; size_t second; } pair_t;

static size_t hash_i16(int16_t v) {
    uint32_t x = (uint16_t)v * 2654435761u;  /* Fibonacci hashing spreads low bits */
    return (size_t)(x >> 16);
}

bool pair_sum(const int16_t *values, size_t n, int32_t target,
              hash_slot_t *table, size_t cap, pair_t *out) {
    if (values == NULL || table == NULL || out == NULL ||
        cap == 0u || (cap & (cap - 1u)) != 0u) return false;
    size_t mask = cap - 1u;
    for (size_t i = 0u; i < n; i++) {
        int32_t need = target - values[i];   /* 32-bit: no int16 wrap */
        if (need >= INT16_MIN && need <= INT16_MAX) {
            /* Probe for a stored partner equal to need. */
            for (size_t p = hash_i16((int16_t)need); ; p = (p + 1u) & mask) {
                if (table[p].state == SLOT_EMPTY) break;
                if (table[p].value == (int16_t)need) {
                    out->first = table[p].index;
                    out->second = i;
                    return true;
                }
            }
        }
        /* Insert values[i] so later elements can find it. */
        bool placed = false;
        for (size_t p = hash_i16(values[i]); ; p = (p + 1u) & mask) {
            if (table[p].state == SLOT_EMPTY) {
                table[p].state = SLOT_USED;
                table[p].value = values[i];
                table[p].index = i;
                placed = true;
                break;
            }
            if (table[p].value == values[i]) break;  /* keep earliest index */
            if (p == (hash_i16(values[i]) + mask) % cap) break; /* full lap */
        }
        if (!placed && table[(hash_i16(values[i]) + mask) & mask].state != SLOT_EMPTY) {
            /* table full and value not already stored */
        }
    }
    return false;
}

• Two-sum with a hash table: as you scan, each element asks 'have I already seen target - x?' The table answers in O(1) average, turning O(n^2) brute force into one pass.
• Open addressing with linear probing needs no nodes and no malloc — perfect for a caller-owned static table. cap must be a power of two so (p + 1) & mask wraps cheaply; the function validates that instead of trusting it.
• The complement is computed in int32_t before any cast: target - x can exceed int16_t range even when both inputs are int16_t, and wrapping there invents phantom pairs.
• Insert happens after the lookup so an element never pairs with itself; storing only the earliest index of a duplicate keeps answers deterministic.
• Sizing guidance: load factor above ~0.7 makes linear probing cluster, so the recommended cap >= 2*n keeps probes near O(1).

Cases the tests must cover

• [2,7,11,15] target 9 → indices (0,1)
• Duplicate needed twice: [3,3] target 6 → (0,1); [3] target 6 → false
• No pair returns false and table is left consistent
• Table at 2x capacity with adversarial values still terminates
• target 40000 (out of int16 pair reach) returns false cleanly

How it gets written wrong

• Subtracting in int16_t: 30000 - (-30000) wraps negative and matches a pair that does not exist.
• Inserting before lookup, letting x pair with itself when 2*x == target but x appears once.
• Non-power-of-two cap with & mask: slots alias and the probe sequence skips entries.
• No full-table termination: probing an entirely USED table loops forever.

Easy - First Entry Above Threshold

Threshold crossing on a sorted table: the first calibration point above a reading, the first timer deadline after now, the first free block above a size class.

Return the index of the first sorted calibration entry strictly greater than the query (upper bound). Handle empty tables and queries beyond the last entry.

Upper bound over a calibration table

Returns the first index whose entry is strictly greater than query, or n when none exists. Empty tables return 0.

#include <assert.h>
#include <stddef.h>
#include <stdint.h>

/* Invariant over half-open [lo,hi): entries left of lo are <= query. */
size_t upper_bound_u16(const uint16_t *table, size_t n, uint16_t query)
{
    size_t lo = 0U, hi = n;
    while (lo < hi) {
        size_t mid = lo + (hi - lo) / 2U;   /* overflow-free midpoint */
        if (table[mid] <= query) lo = mid + 1U;
        else hi = mid;
    }
    return lo;
}

int main(void)
{
    uint16_t t[] = { 10U, 20U, 20U, 30U };
    assert(upper_bound_u16(t, 4U, 20U) == 3U);
    assert(upper_bound_u16(t, 4U, 5U) == 0U);
    assert(upper_bound_u16(t, 4U, 30U) == 4U);
    assert(upper_bound_u16(NULL, 0U, 1U) == 0U);
    return 0;
}

• <= moves lo past duplicates, so the result sits AFTER every equal entry.
• lo + (hi - lo)/2 cannot overflow; (lo + hi)/2 can on huge tables.
• n is a valid result meaning every entry is <= query.

Cases the tests must cover

• duplicates: first index after the run
• query below all returns 0
• query above all returns n
• empty table returns 0
• single entry less than query returns 1

How it gets written wrong

• Using < instead of <= returns the FIRST equal entry (that is lower_bound).
• A closed-interval loop with hi = n-1 re-tests and can loop forever.

Medium - Peak of a Unimodal Sweep

Finding a local maximum in a scan without sorting: the resonant point in an impedance sweep, the focus peak in a lens sweep, the strongest channel in an RF scan.

Given sensor readings that strictly rise then strictly fall, find the peak index in logarithmic time. The contract requires a valid unimodal, non-empty array.

Peak of a unimodal sweep

Requires a non-empty strictly unimodal array (rises then falls). Returns the index of the maximum.

#include <assert.h>
#include <stddef.h>
#include <stdint.h>

size_t peak_index(const int16_t *a, size_t n)
{
    size_t lo = 0U, hi = n - 1U;
    while (lo < hi) {
        size_t mid = lo + (hi - lo) / 2U;
        if (a[mid] < a[mid + 1U]) lo = mid + 1U;   /* still climbing: peak right */
        else hi = mid;                             /* falling: peak at or left */
    }
    return lo;
}

int main(void)
{
    int16_t a[] = { 1, 3, 8, 9, 7, 2 };
    int16_t one[] = { 42 };
    assert(peak_index(a, 6U) == 3U);
    assert(peak_index(one, 1U) == 0U);
    return 0;
}

• Comparing a[mid] with a[mid+1] tells you which side of the peak you are on.
• hi = mid (not mid-1) keeps the peak inside the range; lo = mid+1 guarantees progress.
• The loop ends with lo == hi on the maximum.

Cases the tests must cover

• peak interior
• single element
• two-element rising array returns index 1
• peak at index 0 of a falling pair
• long plateau-free sweep stays logarithmic

How it gets written wrong

• A linear max scan is O(n): too slow per sweep on a small MCU at high rates.
• Equal neighbors violate strict unimodality; state the contract instead of guessing.

More in Embedded DSA

• The WorkbenchA complete embedded-first DSA course with theory, 80 challenges, complete C11 implementations, visual traces, mastery tracking, interview drills, and a constraint-driven firmware design arena.
• Arrays & WindowsTwo pointers, sliding windows, in-place compaction and streaming filters over sample buffers. Twelve problems with complete C11 solutions, complexity targets and edge-case tests.
• Lists, Pools & ArenasIntrusive linked lists, fixed-block pools, arena allocators and why malloc is banned in most firmware. Ten problems on owning memory with a bound you can prove before the board ships.
• Trees, Graphs & StateTries for command tables, union-find for connectivity, and state machines that cannot reach an undefined state. Nine problems on structures that encode relationships rather than sequences.
• Parsing & ProtocolsFraming, COBS, incremental parsers and adversarial input. Nine problems on decoding a byte stream from a hostile world without a buffer overflow or an unbounded loop.
• Linked ListsEvery list variant, written for embedded C rather than for a whiteboard: singly and doubly linked, circular lists and sentinels that delete the boundary cases, the intrusive form kernels and firmware actually use, static pools and free lists for systems without malloc, reversal and cycle detection, and an honest account of when an array is the better answer.
• Sorting Under ConstraintWhich sort survives a 512-byte stack and a fixed deadline. Insertion sort for small nearly-sorted windows, heapsort when the worst case must be provable, counting sort for byte keys, and a bounded-depth quicksort - six problems with complete C11 solutions.
• Heaps & SchedulingBinary heaps as timer wheels and task schedulers, and wrap-safe time comparison - the bug that only shows up 49 days after the board is deployed. Eight problems with complete solutions.
• Integer & Fixed-Point MathComputing the right number with no floating-point unit. Q formats, multiply-before-divide, rounding instead of truncating, division by a constant as a multiply and shift, running averages that do not stall, and LFSR jitter for backoff.
• Stacks, Queues & RingsThe ring buffer and the SPSC queue: the two structures every firmware project actually ships. Ownership between an ISR and a main loop, overflow policy, and why the full/empty test is where the bugs are.
• Bits & BytesRegister fields, bit reversal, parity, endianness and portable packet decoding, without invoking undefined behaviour. Seven problems with complete C11 solutions and a step-by-step trace for each.
• Firmware CapstonesSix full-system problems: DMA ownership, wear-levelled persistence, crash-safe logging and proving a design meets its RAM and WCET budget. This is where every earlier stage gets used at once.