Search strategies

SearchStrategy

Abstract supertype for sorted-search strategies. Two flavours of concrete subtype:

• Singleton strategies (LinearScan, SIMDLinearScan, BracketGallop, ExpFromLeft, InterpolationSearch, BitInterpolationSearch, BinaryBracket, UniformStep, BisectThenSIMD) are zero-field structs. Each one has a matching StrategyKind enum value; pass either the struct or its enum tag to searchsorted_last / searchsorted_first. The struct form forwards through strategy_kind and constant-folds for a literal strategy, so it compiles to the same code as the enum tag.
• Stateful strategies (Auto, GuesserHint) carry per-instance data. They dispatch via their own searchsorted_last / searchsorted_first multimethods.

Strategies can also be passed to the batched searchsortedlast! / searchsortedfirst! APIs.

StrategyKind

Enum tag identifying a singleton search strategy. Use values of this enum as the first positional argument to searchsorted_last and searchsorted_first:

searchsorted_last(KIND_BRACKET_GALLOP, v, x, hint)

Each tag corresponds to one of the singleton strategy types (e.g. KIND_BRACKET_GALLOP ↔ BracketGallop). Stateful strategies (GuesserHint) do not have an enum tag — they dispatch through their wrapper struct directly.

The enum is stored as UInt8 so passing it through to dispatcher functions costs the same as a Bool and does not enlarge any struct that carries it.

searchsorted_last(kind::StrategyKind, v, x[, hint]; order = Base.Order.Forward)
searchsorted_last(s, v, x[, hint]; order = Base.Order.Forward)

FFF-owned positional search for the largest index i with v[i] ≤ x under order (or v[i] ≥ x under Base.Order.Reverse). The polarity matches Base.searchsortedlast.

v must be sorted in ascending order under order. Like Base.searchsortedlast, the precondition is assumed, not checked — the result on unsorted v is undefined.

When the first argument is a StrategyKind value the call dispatches via a runtime if/elseif branch on the enum into the matching kernel. When the first argument is a stateful strategy wrapper (Auto, GuesserHint) the call dispatches via multimethod into that wrapper's own searchsorted_last method.

This is the only search entry point: as of v3, FindFirstFunctions no longer extends Base.searchsortedlast / Base.searchsortedfirst with strategy methods.

searchsorted_first(kind::StrategyKind, v, x[, hint]; order = Base.Order.Forward)
searchsorted_first(s, v, x[, hint]; order = Base.Order.Forward)

FFF-owned positional search for the smallest index i with v[i] ≥ x under order (or v[i] ≤ x under Base.Order.Reverse). As with searchsorted_last, v must be sorted in ascending order under order (assumed, not checked). See searchsorted_last for the dispatch story.

strategy_kind(s::SearchStrategy) -> StrategyKind

Map a singleton strategy struct to its enum tag. Auto returns its stored resolved kind. GuesserHint (genuinely stateful, no singleton tag) throws ArgumentError.

LinearScan <: SearchStrategy

Walk ±1 from the hint. Best when the target is within a few positions of the hint. Falls back to BinaryBracket when no hint is supplied.

Maps to KIND_LINEAR_SCAN.

SIMDLinearScan <: SearchStrategy

Variant of LinearScan whose forward walk is lowered to 8-wide SIMD chunks via custom LLVM IR. Specialized for DenseVector{Int64} and DenseVector{Float64}; for any other element type, falls back to plain LinearScan. The backward walk (when the hint is past the answer) uses the scalar LinearScan path regardless of element type.

Maps to KIND_SIMD_LINEAR_SCAN.

Wins on long forward walks (≥ 8 elements past the hint). For walks of 1–3 elements LinearScan is comparable — the SIMD chunk has constant setup overhead. Worst case is O(n / 8) which is still linear, so SIMDLinearScan is only Auto-relevant for small n or small-gap batches where plain LinearScan would have been picked anyway.

Caveats:

• Element type must be exactly Int64 or Float64.
• Sorted-Float64 vectors containing NaN produce undefined results.
• Falls back to BinaryBracket when no hint is supplied.
• Falls back to LinearScan for non-Forward orderings.

BracketGallop <: SearchStrategy

Expand an exponential bracket bidirectionally from the hint, then binary-search inside the bracket. Effectively O(1) when the target is near the hint; never worse than ~2 log₂ n comparisons.

Maps to KIND_BRACKET_GALLOP. Falls back to BinaryBracket when no hint is supplied.

ExpFromLeft <: SearchStrategy

Exponential search forward from the hint (interpreted as a left bound), then binary search in the final bracket. Best for batched sorted queries where each next query's hint is the previous result.

Maps to KIND_EXP_FROM_LEFT. Falls back to BinaryBracket when no hint is supplied.

InterpolationSearch <: SearchStrategy

Guesses an index by linearly extrapolating x between v[lo] and v[hi], then refines with a bounded binary search.

Maps to KIND_INTERPOLATION_SEARCH. Ignores any hint. Falls back to BinaryBracket for non-numeric element types.

BitInterpolationSearch <: SearchStrategy

Variant of InterpolationSearch that reinterprets DenseVector{Float64} as DenseVector{UInt64} before computing the extrapolation guess. Wins on log-spaced (geometric) data.

Maps to KIND_BIT_INTERPOLATION_SEARCH.

Constraints:

• DenseVector{Float64} only.
• Requires v[1] > 0 and the query x > 0.
• Forward / Reverse orderings only.

Opt-in only — Auto does not pick this strategy. Falls back to InterpolationSearch for non-Float64 dense eltypes, and to BinaryBracket for non-positive or non-finite Float64 data.

BinaryBracket <: SearchStrategy

Plain Base.searchsortedlast / Base.searchsortedfirst. Ignores any hint.

Maps to KIND_BINARY_BRACKET.

BisectThenSIMD <: SearchStrategy

Equality-search strategy. Binary-bisects v down to a small basecase, then SIMD-scans the basecase for exact equality with x. Specialised for DenseVector{Int64} + Int64 queries.

Maps to KIND_BISECT_THEN_SIMD. Meant for use with findequal, not with searchsortedfirst / searchsortedlast — in the positional API it falls back to BinaryBracket.

UniformStep <: SearchStrategy

O(1) direct-arithmetic lookup for uniformly-spaced vectors.

Maps to KIND_UNIFORM_STEP. Specialized for AbstractRange{<:Real}; for other vector types, falls back to BinaryBracket. Ignores any hint.

Auto <: SearchStrategy
Auto()
Auto(props::SearchProperties)
Auto(v::AbstractVector)
Auto(v::AbstractVector, props::SearchProperties)

Stateful strategy that resolves to a concrete StrategyKind at construction time. The resolution uses static information available at construction: props (if supplied) plus v (if supplied).

Per-query (searchsorted_last(Auto(), v, x[, hint])): forwards directly to the stored kind. Auto() defaults to KIND_BINARY_BRACKET (safe choice when nothing is known about v); Auto(v) resolves to a faster kind based on length(v), props.is_uniform, etc. Callers that want the v2-era "pick at every query based on length and hint" behaviour should explicitly construct Auto(v) for each new v.

Batched sorted (searchsortedlast!(out, v, queries; strategy = Auto())): the batched dispatcher re-resolves the kind from (v, queries) even when Auto() carries the default kind — the gap-based decision tree requires the queries, which aren't available at Auto-construction time.

Cached properties. Passing a populated SearchProperties via Auto(props) or Auto(v, props) short-circuits the per-call probes. The cached path is behaviour-equivalent to Auto(v) when props is up to date for v; the caller is responsible for re-computing props if v mutates.

Fields

• kind::StrategyKind — resolved kind. Use this field directly in hot loops via searchsorted_last(auto.kind, v, x, hint) to skip the auto.props field load entirely.
• props::SearchProperties — cached properties used by the batched decision tree.

SearchProperties{T}

Cached, non-allocating facts about a sorted vector. Pass to Auto via Auto(props) to skip the per-call probes that the default Auto() runs on every batched call.

Default-constructed (SearchProperties()) is the "no information" sentinel: has_props is false, the other fields are unspecified and ignored by Auto. Construct via SearchProperties(v::AbstractVector) to populate the fields by running the probes once.

T is the data ratio type — the type of oneunit(eltype(v)) / oneunit(eltype(v)), so e.g. SearchProperties{Float64} for Vector{Int} (because Int/Int promotes to Float64) or Vector{Float64}, SearchProperties{Float32} for Vector{Float32}. For non-Number eltypes the default is Float64 and has_props = false.

Currently consumed by Auto:

• is_linear — gates InterpolationSearch in batched dispatch.
• has_nan (Float64 only) — gates SIMDLinearScan eligibility.
• is_uniform — short-circuits to UniformStep when set, with first_val and inv_step baked in for closed-form O(1) lookup.

When is_uniform = true, first_val and inv_step hold the precomputed data needed by UniformStep's closed-form path (idx = floor((x - first_val) * inv_step) + 1). When is_uniform = false they are zero(T) and never consulted.

The is_log_linear field is populated for callers that want to manually pin BitInterpolationSearch; Auto does not consume it.

findequal(strategy, v, x[, hint]; order = Base.Order.Forward) -> Int

Return the index of x in sorted v if present, or the sentinel firstindex(v) - 1 if x is absent. Type-stable Int return — the sentinel matches the convention Base.searchsortedlast already uses for "x precedes all of v".

The strategy argument can be:

• A singleton strategy struct (BinaryBracket(), BracketGallop(), …) — forwards through the struct → kind mapping.
• A StrategyKind enum value (KIND_BRACKET_GALLOP, …).
• A stateful strategy (Auto, GuesserHint) — dispatched via multimethod.

Most strategies are handled generically. The shortcut method on BisectThenSIMD for DenseVector{Int64} skips the searchsortedfirst path entirely.

For unsorted vectors, use findfirstequal.