Introduction

The fastest way to search whether a number belongs to any range depends on whether the ranges are static or changing. For one-off checks, a simple scan may be enough. For repeated queries over a fixed set of ranges, sorting and binary search are usually the best baseline. The real optimization starts by normalizing overlapping ranges before you search.

Start by Merging Overlapping Ranges

If ranges overlap or touch, merge them first. That reduces search space and removes ambiguity.

1def merge_ranges(ranges):
2    ranges = sorted(ranges)
3    merged = []
4
5    for start, end in ranges:
6        if not merged or start > merged[-1][1] + 1:
7            merged.append([start, end])
8        else:
9            merged[-1][1] = max(merged[-1][1], end)
10
11    return merged
12
13print(merge_ranges([(1, 3), (2, 5), (10, 12)]))

Without this step, you may search more intervals than necessary.

Use Binary Search on Sorted Non-Overlapping Ranges

Once the ranges are sorted and merged, binary search gives efficient membership checks.

1def contains(ranges, x):
2    left, right = 0, len(ranges) - 1
3
4    while left <= right:
5        mid = (left + right) // 2
6        start, end = ranges[mid]
7
8        if start <= x <= end:
9            return True
10        if x < start:
11            right = mid - 1
12        else:
13            left = mid + 1
14
15    return False
16
17ranges = merge_ranges([(1, 3), (2, 5), (10, 12)])
18print(contains(ranges, 4))
19print(contains(ranges, 9))

After preprocessing, each query runs in logarithmic time.

This is usually the right answer when the same range set is queried many times. You pay the sorting and merging cost once, then reuse the prepared structure for every lookup.

Know When Linear Search Is Good Enough

If you only search once or the range list is tiny, a linear scan may be simpler and effectively just as good.

def contains_linear(ranges, x):
    return any(start <= x <= end for start, end in ranges)

Optimization only pays off when repeated queries justify the preprocessing cost.

Use Interval Trees Only for Dynamic or Complex Workloads

If ranges are inserted and removed frequently, or if you need more complex interval queries, an interval tree or segment tree may be appropriate. For static membership lookup, though, that is usually unnecessary complexity compared with merged sorted ranges plus binary search.

The simplest correct structure should usually win.

Another useful variation is to keep two parallel arrays, one for range starts and one for range ends, after merging. That can make binary search code slightly cleaner in some languages or codebases, but the underlying idea is the same: search over normalized intervals, not raw overlapping input.

The important optimization is conceptual, not stylistic: preprocess once, then query many times against the reduced structure.

That is why benchmark results change so much depending on query volume. For one query, preprocessing may dominate. For thousands, preprocessing is usually the right trade. Static workloads benefit most. Repeated queries justify the setup cost. That pattern appears often. Especially.

Common Pitfalls

• Searching unsorted overlapping ranges with binary search and expecting correct results.
• Forgetting to merge intervals before optimizing lookup.
• Building a heavy interval-tree solution for a small static range set.
• Ignoring whether the workload is one query or thousands of repeated queries.
• Treating touching ranges as separate when the application could normalize them safely.

Summary

• For repeated membership checks, merge ranges first and then binary search.
• Merging overlapping ranges reduces both complexity and search cost.
• Linear search is still fine for one-off or very small inputs.
• Use more advanced interval structures only when the workload really demands them.
• The fastest practical solution is usually sorted merged intervals plus binary search.