7.9 Interval Search

Many search problems involve ranges rather than individual values.

A database query may ask for all orders placed between two timestamps. A monitoring system may need all measurements within a temperature range. A search engine may retrieve documents whose scores fall between two thresholds. In each case, the objective is not to locate a single value but to identify a contiguous interval of matching records.

A common mistake is to find one matching value and then scan outward to locate the rest. This approach often turns a logarithmic search into a linear one. A better strategy uses lower bounds and upper bounds to locate the entire interval directly.

The central idea is simple: find where the interval begins and where it ends. Once those boundaries are known, every matching value lies between them.

Problem

Given a sorted array and a range:

[minValue, maxValue]

find all elements that fall inside the range.

Example:

nums = [1, 3, 4, 4, 4, 6, 8, 9, 11]

Query:

[4, 8]

Expected result:

[4, 4, 4, 6, 8]

A linear scan works:

func RangeSearchLinear(
	nums []int,
	minValue int,
	maxValue int,
) []int {

	var result []int

	for _, value := range nums {
		if value >= minValue &&
			value <= maxValue {
			result = append(result, value)
		}
	}

	return result
}

Time complexity:

O(n)

When the collection contains millions of values, scanning everything becomes expensive.

Solution

Locate the left boundary using lower bound.

Locate the right boundary using upper bound.

func LowerBound(
	nums []int,
	target int,
) int {

	lo, hi := 0, len(nums)

	for lo < hi {
		mid := lo + (hi-lo)/2

		if nums[mid] >= target {
			hi = mid
		} else {
			lo = mid + 1
		}
	}

	return lo
}

func UpperBound(
	nums []int,
	target int,
) int {

	lo, hi := 0, len(nums)

	for lo < hi {
		mid := lo + (hi-lo)/2

		if nums[mid] > target {
			hi = mid
		} else {
			lo = mid + 1
		}
	}

	return lo
}

Range search becomes:

func RangeSearch(
	nums []int,
	minValue int,
	maxValue int,
) []int {

	left := LowerBound(nums, minValue)
	right := UpperBound(nums, maxValue)

	return nums[left:right]
}

Example:

nums := []int{
	1, 3, 4, 4, 4,
	6, 8, 9, 11,
}

fmt.Println(
	RangeSearch(nums, 4, 8),
)

Output:

[4 4 4 6 8]

Understanding the Boundaries

Consider:

nums = [1, 3, 4, 4, 4, 6, 8, 9, 11]

Range:

[4, 8]

Lower bound of 4:

index = 2

Upper bound of 8:

index = 7

Visualized:

Index: 0 1 2 3 4 5 6 7 8
Value: 1 3 4 4 4 6 8 9 11
          |         |
        left      right

Every matching value lies inside:

[left, right)

No scanning is required to discover the interval.

Finding Exact Ranges

Suppose you want all occurrences of:

The query becomes:

[4, 4]

Compute:

left := LowerBound(nums, 4)
right := UpperBound(nums, 4)

Results:

left  = 2
right = 5

Therefore:

nums[2:5]

contains every occurrence.

Output:

[4, 4, 4]

This technique is widely used in frequency analysis and search indexes.

Counting Values in a Range

Sometimes the actual values are unnecessary.

You only need the count.

Example:

How many values lie between
100 and 500?

Using interval boundaries:

count :=
	UpperBound(nums, 500) -
	LowerBound(nums, 100)

No values are copied.

No iteration is required.

The count is obtained directly from the interval width.

This pattern appears frequently in analytics engines and database query planners.

Timestamp Queries

Consider sorted timestamps:

Query:

09:15 - 10:15

Lower bound finds:

09:17

Upper bound finds:

10:41

The interval becomes:

Many event-processing systems use exactly this strategy.

The timestamps may be stored in arrays, B-trees, LSM trees, or distributed indexes, but the underlying operation remains an interval search.

Searching Ordered Records

The values being searched need not be integers.

Suppose employees are ordered by salary.

type Employee struct {
	Name   string
	Salary int
}

Find employees earning between:

100000
150000

Binary search locates the first employee meeting the minimum salary requirement and the first employee exceeding the maximum salary.

The resulting interval contains every matching record.

This approach scales naturally to millions of records.

Database Indexes

Consider a database index:

Query:

WHERE score BETWEEN 140 AND 240

Conceptually, the database performs:

LowerBound(140)
UpperBound(240)

Result:

Most modern storage engines optimize range queries using this principle.

The difference between a point lookup and a range scan is often just the number of values returned after the boundaries have been located.

Prefix Searches

String searches can also be treated as interval searches.

Suppose:

apple
application
apply
banana
car

Query:

Prefix = "app"

Lower bound:

"app"

Upper bound:

first string greater than
all values beginning with app

The resulting interval contains:

apple
application
apply

Search engines, autocomplete systems, and dictionary indexes rely heavily on this technique.

Multi-Dimensional Extensions

The one-dimensional interval search generalizes to higher dimensions.

Examples include:

Latitude range
Longitude range

or:

Price range
Date range

Specialized structures such as range trees, k-d trees, R-trees, and segment trees extend the same idea into multiple dimensions.

The underlying principle remains unchanged:

Locate the boundaries.
Restrict processing to the candidate region.

Why Interval Search Matters

Many algorithms focus on locating a single value.

Real systems often care more about groups of values.

Examples include:

All customers in a region
All logs during a time window
All products within a price range
All transactions in a period
All records matching a score range

Boundary searches naturally solve these problems.

In practice, interval queries are often more important than exact lookups.

Complexity Analysis

Finding the left boundary:

O(log n)

Finding the right boundary:

O(log n)

Total search cost:

O(log n)

Extracting results:

O(k)

where:

k = number of matching values

Overall complexity:

O(log n + k)

This is optimal because every returned value must eventually be examined.

Common Mistakes

A common error is locating one matching value and then expanding outward linearly.

For large duplicate ranges, this can degrade performance significantly.

Another mistake is treating the right boundary as inclusive.

The upper-bound result is exclusive.

The interval should always be interpreted as:

[left, right)

A third mistake is forgetting that the interval may be empty.

Example:

[50, 60]

inside:

[1, 2, 3, 4]

Both boundaries may evaluate to the same position.

This correctly represents an empty result set.

Takeaway

Interval search transforms range queries into boundary-finding problems. By combining lower bound and upper bound searches, you can locate all matching values, count them, or process them without scanning unrelated data. This pattern forms the foundation of range indexes, database scans, analytics systems, search engines, and time-series storage. Once you begin viewing ranges as pairs of boundaries, a large class of search problems becomes both simpler and more efficient.