Introduction

Range lookup appears in pricing rules, time windows, access policies, and telemetry bucketing. The right algorithm depends less on raw speed claims and more on interval properties such as overlap, updates, and query volume. This guide explains practical choices and shows runnable code for static and dynamic scenarios.

Problem Shape and Constraints

Given a value and a set of intervals, you want to return the interval that contains the value, or all matching intervals if overlap is allowed. Before choosing a structure, answer four questions:

• Are intervals disjoint or overlapping.
• Are intervals static or frequently updated.
• Do you need one match or all matches.
• Is memory tight or plentiful.

If intervals are disjoint and sorted, you can answer each query in logarithmic time with binary search. If overlap is heavy and updates happen, an interval tree is usually better.

Fast Path for Disjoint Sorted Ranges

For disjoint intervals, store starts and ends in order by start. Query by finding the rightmost interval whose start is not greater than the value. Then test whether value is within that interval end.

1from bisect import bisect_right
2from typing import List, Optional, Tuple
3
4Range = Tuple[int, int]
5
6
7def find_range_disjoint(ranges: List[Range], x: int) -> Optional[Range]:
8    # ranges must be sorted and non-overlapping
9    starts = [a for a, _ in ranges]
10    i = bisect_right(starts, x) - 1
11    if i < 0:
12        return None
13    a, b = ranges[i]
14    return (a, b) if a <= x <= b else None
15
16
17ranges = [(1, 5), (10, 15), (20, 30)]
18for x in [0, 3, 12, 18, 27]:
19    print(x, find_range_disjoint(ranges, x))

Complexity:

• Build time is linear if already sorted, or O(n log n) including sort.
• Query time is O(log n).
• Extra memory is O(n) for stored intervals and starts.

This is usually the best baseline for static disjoint ranges.

Handling Overlap with an Interval Tree

When many ranges overlap and you need all matches, binary search on starts alone is not enough. Interval trees augment each node with a maximum end value in its subtree, allowing branch pruning.

Simple approach in Python uses a library implementation:

1from intervaltree import IntervalTree
2
3# Half-open intervals: [begin, end)
4tree = IntervalTree.from_tuples([
5    (1, 6),
6    (4, 9),
7    (10, 20),
8    (15, 18),
9])
10
11x = 5
12hits = sorted(tree.at(x), key=lambda iv: (iv.begin, iv.end))
13print([(iv.begin, iv.end) for iv in hits])

Why this helps:

• Query cost is around logarithmic plus number of returned hits.
• Works well for overlap-heavy datasets.
• Supports insert and remove without full rebuild.

Tradeoff is memory and implementation complexity compared with a flat array.

Preprocessing and Validation

Many lookup bugs come from dirty intervals, not query logic. Validate at load time.

1def normalize_ranges(ranges):
2    clean = []
3    for a, b in ranges:
4        if a > b:
5            a, b = b, a
6        clean.append((a, b))
7    clean.sort()
8    return clean
9
10
11def assert_disjoint(sorted_ranges):
12    for i in range(1, len(sorted_ranges)):
13        prev = sorted_ranges[i - 1]
14        cur = sorted_ranges[i]
15        if cur[0] <= prev[1]:
16            raise ValueError("overlap detected")

For boundaries, decide one convention and keep it global:

• Closed intervals, meaning both ends included.
• Half-open intervals, meaning start included and end excluded.

Half-open is common in programming because adjacent ranges join cleanly without ambiguity.

Throughput Tactics

If queries dominate and ranges are static:

• Build once and reuse immutable structures.
• Keep intervals in contiguous arrays for cache locality.
• Avoid object-heavy representations in hot loops.

If updates are frequent:

• Use interval tree or balanced tree approach.
• Batch updates when possible to reduce rebalance overhead.

If domain is small integer space:

• Direct indexing table may beat trees and searches.
• Memory can be large, so use only when domain is bounded and dense.

Common Pitfalls

• Running linear scan for every query in high-throughput systems. Fix by sorting and using binary search or an interval tree.
• Mixing closed and half-open interval semantics. Fix by writing a boundary contract in code comments and tests.
• Ignoring overlap assumptions. Fix by validating intervals on load and choosing structure accordingly.
• Rebuilding structures per query. Fix by preprocessing once and reusing the index.
• Optimizing before measuring. Fix by benchmarking with realistic interval distributions and query mixes.

Summary

• Disjoint sorted intervals are best served by binary search with O(log n) queries.
• Overlapping intervals usually require interval-tree style indexing.
• Correctness starts with interval normalization and boundary rules.
• Structure choice should follow data characteristics, not generic speed claims.
• Benchmark with production-like inputs before finalizing the implementation.