Search Policies

This page explains each search policy in detail, including when to use it and how it works internally.

AutoSearch (Default) — Recommended for All Use Cases

Automatically selects BinarySearch() or LinearBinarySearch() based on query type, hint presence, and data access pattern at call time. This is the default for all interpolants — no configuration needed.

Resolution rules:

itp = linear_interp(x, y)  # stores AutoSearch (the default)
itp(0.5)          # → BinarySearch() (scalar query)
itp(sorted_xs)    # → LinearBinarySearch() (sorted detected)
itp(rand_xs)      # → BinarySearch() (random detected)
itp.(xs)          # → BinarySearch() per element (broadcast)

# Hint auto-upgrade (scalar + hint → LinearBinarySearch)
hint = Ref(1)
itp(0.5; hint=hint)  # → LinearBinarySearch() (hint implies locality)

# Override when you know the pattern in advance:
itp(0.5; search=BinarySearch())             # force BinarySearch
itp(sorted_xs; search=LinearBinarySearch()) # force LinearBinarySearch

How it works: AutoSearch is resolved in two phases at the call site, not at construction time:

1. Policy resolution (_resolve_search): Picks BinarySearch or LinearBinarySearch based on query type and, for vector queries without a hint, a prefix monotonicity check on the first 8 elements.
2. Searcher creation (_to_searcher): When a Ref{Int} hint is provided alongside BinarySearch, it auto-upgrades to LinearBinarySearch — because the hint implies the caller expects walk-based locality (e.g., SeriesInterpolant scalar evaluation).

When to override with an explicit policy:

• You know queries are always random → explicit BinarySearch() skips the adaptive check (marginal benefit)
• You know queries are always sorted → explicit LinearBinarySearch() skips the adaptive check (marginal benefit)
• For most use cases, keeping AutoSearch() is the right choice — the adaptive overhead is negligible

BinarySearch

Pure binary search. Stateless, thread-safe, no setup required.

Complexity: O(log n) per query

When to use:

• Random access patterns
• One-off queries
• When you want consistent O(log n) for any query order

itp = linear_interp(x, y)
val = itp(0.5)                          # AutoSearch → BinarySearch() for scalar
val = itp(0.5; search=BinarySearch())   # explicit BinarySearch

How it works: Standard binary search on the grid. Each query starts fresh with no memory of previous queries.

LinearBinarySearch

Performs a bounded linear search from the hint position, with automatic binary fallback. This is the safe explicit choice for sorted or monotonic queries — and what AutoSearch resolves to when it detects sorted data.

Complexity: O(1) within the linear window, O(log n) fallback

When to use:

• Sorted query sequences
• Monotonically increasing time (ODE solvers)
• Streaming data with local continuity
• Any case where you'd consider LinearSearch() — LinearBinarySearch() is almost always the better choice

sorted_queries = sort(rand(1000))
itp = linear_interp(x, y; search=LinearBinarySearch())
vals = itp(sorted_queries)  # O(1) amortized for sorted input

How it works: Starting from the hint position, walks linearly left or right (up to linear_window). If the target interval isn't found within bounds, falls back to binary search. This fallback guarantees O(log n) worst-case — making it safe for any query pattern.

Tuning linear_window

You can tune the linear search window size before falling back to binary search:

LinearBinarySearch()                   # default: linear_window=8
LinearBinarySearch(linear_window=0)    # hint check only, no walk (minimal random overhead)
LinearBinarySearch(linear_window=4)    # narrow window for tight jitter patterns
LinearBinarySearch(linear_window=16)   # wider window for sparser-spaced sorted queries

Guidelines:

• Zero (0): Hint check only, no walk — minimal random-query overhead. Good when queries cluster in the same interval.
• Small linear_window (1–2): Minimal overhead for mixed query patterns
• Medium values (4): Good for narrow jitter patterns (step size < 2 intervals)
• Default (8): Best balance — +2.5ns random overhead, covers jitter up to ~6 intervals
• Large linear_window (16–128): For wide jitter, highly localized queries, or very large datasets

LinearGallopSearch (Opt-in)

Same direct hit and linear walk as LinearBinarySearch, but when the target lies beyond the window it gallops outward from where the walk stopped (1, 2, 4, 8, … cells) and bisects that bracket, instead of restarting a binary search over the whole grid. This is also known as exponential search, or hunt in Numerical Recipes. AutoSearch never selects it.

Complexity: O(1) within the linear window, O(log gap) beyond it, where gap is the number of cells between consecutive queries

When to use — sorted or local queries that are a moderate distance apart:

• Sampling a long, fine grid at a coarser set of sorted points, e.g. about 10,000–100,000 sorted queries on a 1M-point grid
• Streaming queries with a hint whose steps are tens to hundreds of cells

When not to use — keep the default:

• Random access: galloping across a large part of the grid costs about twice the probes of a binary search
• Very sparse sorted queries (gaps ≳ √n cells), e.g. 10–1,000 queries on a 1M-point grid
• Dense sorted queries (gaps within the window): nothing to gain

itp = linear_interp(x, y)
vals = itp(sorted_queries; search=LinearGallopSearch())   # call-site override
itp = linear_interp(x, y; search=Search(:linear_gallop))  # baked in
LinearGallopSearch(linear_window=16)                      # same curated windows as LinearBinarySearch

LinearSearch (Expert Only)

Pure linear search for strictly monotonic, closely-spaced queries. Scans the grid one interval at a time from the hint until the target is found — no fallback, no window limit.

Complexity: O(1) amortized for monotonic, closely-spaced sequences; O(n) worst case

The only case where LinearSearch() may be justified:

• Tight inner loops where every nanosecond matters
• Queries are guaranteed to be strictly monotonic and closely-spaced (e.g., fixed-step ODE with small dt)
• You have benchmarked and confirmed a measurable advantage over LinearBinarySearch()

When NOT to use (use LinearBinarySearch() or AutoSearch() instead):

• Random access patterns
• Queries that may be far apart
• Large grids with sparse query spacing
• Adaptive-step ODE solvers (step size can vary widely)
• Any general-purpose code

# ONLY if you have benchmarked and confirmed this is faster for your specific case
itp = linear_interp(x, y)
hint = Ref(1)
for t in t_values  # MUST be strictly monotonic and closely-spaced
    y = itp(t; search=LinearSearch(), hint=hint)
end

# Safer alternative that is equally fast for monotonic data:
for t in t_values
    y = itp(t; search=LinearBinarySearch(), hint=hint)
end

How it works: Walks linearly from the hint position one interval at a time. Without a step limit, it will traverse the entire grid if necessary — which is optimal for close queries but catastrophic for distant ones.

Performance Summary

AutoSearch() adapts to your data: it detects sorted queries and uses LinearBinarySearch, detects random queries and falls back to BinarySearch. You get near-optimal performance for both patterns without choosing manually.

Baked-in vs Override

Baked-in Policy (Constructor)

Override the default AutoSearch when creating the interpolant. The stored policy applies to all subsequent calls:

itp = linear_interp(x, y)                              # AutoSearch() — adapts per call
itp = linear_interp(x, y; search=BinarySearch())       # always BinarySearch()
itp = linear_interp(x, y; search=LinearBinarySearch()) # always LinearBinarySearch()

Override at Call Time

Override the stored policy for a single call without changing the interpolant:

itp = linear_interp(x, y)  # stores AutoSearch (default)

# Call-site override — does not change itp.search_policy
val  = itp(0.5; search=BinarySearch())             # force BinarySearch for this call
vals = itp(sorted_xs; search=LinearBinarySearch()) # force LinearBinarySearch for this call

This is useful when most queries benefit from one policy, but occasional queries need different behavior.

See Also

• Overview — Quick decision matrix
• Using Hints — External hints for maximum performance