GitHub

Search & Hints Overview

Search policies control how interpolants find the correct grid interval for a query point. Choosing the right policy can significantly improve performance for specific access patterns.

This page applies to Vector grids

For uniform grids, use Range instead—lookup is always O(1) regardless of search policy. See Grid Selection for details. This page focuses on Vector grids where choosing the right search policy matters.

How It Works

Every interpolation query on a Vector grid requires finding which interval contains the query point. By default, this uses binary search (O(log n)), but for sequential or streaming queries, hinted search can achieve O(1) amortized lookup.

Quick Examples

using FastInterpolations

x = collect(range(0, 1.0, length=1000))
y = x.^3

# For random queries
xq = rand(1000)
linear_interp(x, y, xq; search=Binary())         # Default: optimal for random access
linear_interp(x, y, xq; search=LinearBinary())  # Could be slower

# For sorted/monotonic queries
xq_sorted = sort(xq)
linear_interp(x, y, xq_sorted; search=Binary())         # Same as random
linear_interp(x, y, xq_sorted; search=LinearBinary())  # Much faster!

Decision Matrix

PolicyBest ForComplexityThread Safety
Binary()Random access (default)O(log n)✓ Stateless
HintedBinary()Repeated queries in same regionO(1) hit, O(log n) miss✓ With hint
LinearBinary()Monotonic queries (recommended)O(1) local, O(log n) fallback✓ With hint
Linear()Close + monotonic queries (expert)O(1) amortized✓ With hint
Why No Hunt Algorithm?

The Hunt (correlated) algorithm offers theoretical O(log k) for nearby queries and O(log n) worst-case. However, our benchmarks showed no practical advantage over existing policies—each access pattern already has a better-suited option.

Quick Selection Guide

Which policy should I use?

  • Random access / general use → Binary() (default, most consistent performance)
  • Queries cluster in same region → HintedBinary()
  • Monotonic queries (sorted, streaming, ODE) → LinearBinary() ✅ recommended
  • Strictly monotonic, performance-critical → Linear() (benchmark first! see below)
Benchmark Before Choosing Linear()

Linear() can be faster for some monotonic patterns but slower for others. Always benchmark with your actual query patterns.

Next Steps