Skip to content

stdlib.search

Search Algorithms

Generated from v0.60.1. 6 source files, 37 documented symbols.

binary.xi

fn binary_search(v: &Vec[Int], target: Int) -> Option[Int]

Index of target in a sorted v, or None. O(log n). Requires v to be sorted in non-decreasing order.

  • Postcondition: result is Some(_) => result.value >= 0 && result.value < v.len()
fn binary_search_range(v: &Vec[Int], target: Int, lo: Int, hi: Int) -> Option[Int]

Binary search restricted to the inclusive range v[lo..=hi]. O(log n). Returns None when the range is empty, inverted, or out of bounds.

  • Postcondition: result is Some(_) => result.value >= 0 && result.value < v.len()
fn lower_bound(v: &Vec[Int], target: Int) -> Int

Index of the first element >= target; v.len() if none. O(log n). Requires v to be sorted.

  • Postcondition: result >= 0 && result <= v.len()
fn upper_bound(v: &Vec[Int], target: Int) -> Int

Index of the first element > target; v.len() if none. O(log n). Requires v to be sorted.

  • Postcondition: result >= 0 && result <= v.len()
fn binary_search_by(v: &Vec[Int], target: Int, compare: fn(&Int, &Int) -> Int) -> Option[Int]

Binary search with a custom comparator: compare(&v[mid], &target). O(log n). The comparator must be a named function returning -1/0/1. Requires v to be sorted per the comparator.

  • Postcondition: result is Some(_) => result.value >= 0 && result.value < v.len()
fn search_range(v: &Vec[Int], target: Int) -> (Int, Int)

(lo, hi) tuple: all occurrences of target span the half-open index range [lo, hi). If target is absent, lo == hi (empty range). O(log n).

  • Postcondition: result._0 >= 0 && result._1 >= result._0 && result._1 <= v.len()
fn binary_search_float(v: &Vec[Float64], target: Float64) -> Option[Int]

Binary search for an exact float value in a sorted Vec[Float64]. O(log n). Requires v to be sorted ascending (exact IEEE-754 equality semantics: -0.0 and +0.0 compare equal; NaN never matches because NaN == NaN is false). Returns None when target is absent.

  • Postcondition: result is Some(_) => result.value >= 0 && result.value < v.len()

boyer.xi

fn boyer_moore_bad_char(pattern: Str) -> Vec[Int]

Bad-character shift table indexed by byte value: table[b] is the index of the last occurrence of byte b in pattern, or -1 if b never occurs. O(m).

  • Postcondition: result.len() >= 256
fn boyer_moore_good_suffix(pattern: Str) -> Vec[Int]

Good-suffix shift table: gs[i] is the safe shift when a mismatch occurs at pattern position i. O(m). Computed from the standard suffix array.

fn boyer_moore_search(text: Str, pattern: Str) -> Option[Int]

Start index of the first pattern occurrence in text using the full Boyer-Moore algorithm (bad-character + good-suffix tables). O(n/m) best, O(n*m) worst. Returns None when pattern is empty or longer than text.

  • Postcondition: result is Some(_) => result.value >= 0 && result.value + pattern.len() <= text.len()
fn boyer_moore_search_all(text: Str, pattern: Str) -> Vec[Int]

Start indices of every occurrence of pattern in text (full Boyer-Moore). O(n/m) average. Empty pattern yields an empty result.

  • Postcondition: result.len() >= 0
fn boyer_moore_horspool(text: Str, pattern: Str) -> Option[Int]

Horspool variant of Boyer-Moore: bad-character table only, keyed on the last text character of the window. O(n*m) worst, good average.

  • Postcondition: result is Some(_) => result.value >= 0 && result.value + pattern.len() <= text.len()
fn rabin_karp_hash(s: Str) -> Int

Rolling hash value of the string s. O(len). Uses the fixed base 31 and the Mersenne prime 2^31-1 as modulus; values are always in [0, mod).

fn rabin_karp_search(text: Str, pattern: Str) -> Option[Int]

Rolling-hash substring search. O(n + m) expected, O(n*m) worst on hash collisions. Compares character-by-character when hashes match, so results are exact. Returns None when pattern is empty or longer than text.

interpolation.xi

fn interpolation_search(v: &Vec[Int], target: Int) -> Option[Int]

Index of target via value-proportional probing. O(log log n) average on uniformly distributed sorted Int arrays, O(n) worst. Returns Some(index) or None. Safe on unsorted data (degrades to a probe sequence).

  • Postcondition: result is Some(_) => result.value >= 0 && result.value < v.len()
fn interpolation_search_sorted(v: &Vec[Int], target: Int) -> Option[Int]

Interpolation search assuming the input is already sorted. O(log log n) average, O(n) worst. Identical probing logic to interpolation_search; the separate entry point documents the sortedness precondition.

  • Postcondition: result is Some(_) => result.value >= 0 && result.value < v.len()
fn exponential_search(v: &Vec[Int], target: Int) -> Option[Int]

Exponential (galloping) search: finds a bounding range [2^(k-1), 2^k] then binary-searches it. O(log i) where i is the target index. Requires a sorted vector.

  • Postcondition: result is Some(_) => result.value >= 0 && result.value < v.len()
fn jump_search(v: &Vec[Int], target: Int) -> Option[Int]

Jump search: jumps ahead by sqrt(n) blocks then linearly scans the target block. O(sqrt(n)). Requires a sorted vector.

  • Postcondition: result is Some(_) => result.value >= 0 && result.value < v.len()
fn ternary_search(f: fn(Int) -> Int, lo: Int, hi: Int) -> Int

Ternary search over a unimodal f on [lo, hi]: returns the x maximizing f. O(log n) iterations. f must be a named function; the curve must be strictly unimodal over the range.

fn fibonacci_search(v: &Vec[Int], target: Int) -> Option[Int]

Fibonacci-number-stepped search of a sorted vector. O(log n).

  • Postcondition: result is Some(_) => result.value >= 0 && result.value < v.len()

kmp.xi

fn kmp_prefix_table(pattern: Str) -> Vec[Int]

Longest proper prefix-suffix lengths for each position of pattern. pi[i] is the length of the longest proper prefix of pattern[0..=i] that is also a suffix. O(m). Internal building block exposed for reuse.

  • Postcondition: result.len() == pattern.len()
fn kmp_search(text: Str, pattern: Str) -> Option[Int]

Start index of the first occurrence of pattern in text, or None. O(n + m). Returns None when pattern is empty or longer than text.

  • Postcondition: result is Some(_) => result.value >= 0 && result.value + pattern.len() <= text.len()
fn kmp_search_all(text: Str, pattern: Str) -> Vec[Int]

Start indices of every (overlapping) occurrence of pattern in text. O(n+m). Empty pattern yields an empty result.

  • Postcondition: result.len() >= 0
fn kmp_contains(text: Str, pattern: Str) -> Bool

True if pattern occurs anywhere in text. O(n + m). Empty pattern is false.

fn kmp_count(text: Str, pattern: Str) -> Int

Number of non-overlapping occurrences of pattern in text. O(n + m). Empty pattern yields 0.

  • Postcondition: result >= 0

linear.xi

fn linear_search(v: &Vec[Int], target: Int) -> Option[Int]

Index of the first occurrence of target, or None. O(n). Works on any data.

  • Postcondition: result is Some(_) => result.value >= 0 && result.value < v.len()
fn linear_search_from(v: &Vec[Int], target: Int, start: Int) -> Option[Int]

Index of the first occurrence of target at or after start, or None. O(n). A negative start behaves as 0; a start beyond the end yields None.

  • Postcondition: result is Some(_) => result.value >= 0 && result.value < v.len()
fn linear_search_all(v: &Vec[Int], target: Int) -> Vec[Int]

Indices of every occurrence of target, in ascending order. O(n).

  • Postcondition: result.len() <= v.len()
fn linear_search_by(v: &Vec[Int], pred: fn(&Int) -> Bool) -> Option[Int]

Index of the first element satisfying pred, or None. O(n). Short-circuits. The predicate must be a named function.

search.xi

fn linear_search[T](arr: &Vec[T], target: &T) -> Option[Int]

Linear search -- O(n) worst/average, O(1) best. Scans the array sequentially from index 0. Works on unsorted data. Returns Some(index) of the first match, or None if not found.

fn binary_search[T](arr: &Vec[T], target: &T) -> Option[Int]

Binary search -- O(log n). Requires a sorted array (non-decreasing). Classic divide-and-conquer: repeatedly narrows the range by comparing the middle element against the target. Returns Some(index) if found, or None if not present.

fn interpolation_search(arr: &Vec[Int], target: Int) -> Option[Int]

Interpolation search -- O(log log n) average on uniformly distributed sorted Int arrays, O(n) worst. Analogous to how one searches a phone book: estimates position based on value range. Returns Some(index) if found, or None if not present.

fn exponential_search[T](arr: &Vec[T], target: &T) -> Option[Int]

Exponential search on a sorted slice; returns the index or None.

fn jump_search[T](arr: &Vec[T], target: &T) -> Option[Int]

Jump search on a sorted slice; returns the index or None.

fn lower_bound[T](arr: &Vec[T], target: &T) -> Int

lower_bound -- O(log n). Returns the index of the first element >= target. If all elements are < target, returns arr.len(). Requires sorted array.

fn upper_bound[T](arr: &Vec[T], target: &T) -> Int

upper_bound -- O(log n). Returns the index of the first element > target. If all elements are <= target, returns arr.len(). Requires sorted array.

fn binary_search_range[T](arr: &Vec[T], target: &T) -> (Int, Int)

binary_search_range -- O(log n). Returns (lower_bound, upper_bound) as a tuple: [lo, hi) of all indices where arr[i] == target. If target is not found, lo == hi (empty range). Requires sorted array.