Interval / Range Index (C)
Topics: sorted arrays, binary search, half-open ranges
Problem
Build an index over half-open ranges [start, end) (start inclusive, end
exclusive). Add intervals, then answer two queries: which intervals contain a
point (stabbing), and which overlap a query range (overlapping). Keep the
items sorted by start over caller-provided storage (no allocation) so each query
binary-searches to the relevant prefix and filters by end.
typedef struct { int start, end; char label[32]; } Interval; // end exclusive
typedef struct { Interval *items; size_t cap; size_t count; } IntervalIndex;
void ix_init(IntervalIndex *x, Interval *storage, size_t cap);
void ix_add(IntervalIndex *x, int start, int end, const char *label); // keep sorted by start
size_t ix_stabbing(IntervalIndex *x, int point, Interval *out, size_t maxout); // start<=point<end
size_t ix_overlapping(IntervalIndex *x, int lo, int hi, Interval *out, size_t maxout); // [lo,hi)
ix_add: insert keeping items sorted by start; place a new interval
after any with an equal start so ties preserve insertion order. Results are
always returned in start order.ix_stabbing(point): every match has start <= point, so binary-search the
first index whose start is > point and scan that prefix, keeping those with
end > point.ix_overlapping(lo, hi): a candidate must start before hi, so
binary-search the first index whose start is >= hi and scan that prefix,
keeping those with end > lo.
Key concepts
- Half-open arithmetic:
end is exclusive, so a point equal to end is not
contained, and a query that only touches an interval's end does not overlap.
- Binary search to a prefix: sorting by start means all candidates live in a
contiguous prefix; the upper/lower bound finds where it ends, turning a scan of
everything into a scan of just the prefix.
- Filter by end: the prefix bounds
start; the end > point / end > lo
test is what actually decides containment / overlap.
Run
cc -std=c11 -O2 -Wall tests.c -o /tmp/intervals && /tmp/intervals
Sign in to submit your solution.