rust 41 lines · 7 steps

Prefix search with binary partitioning in Rust

A sorted string index answers prefix queries in logarithmic time using partition_point on a case-insensitive ordering.

Explained by highlit
Intermediate binary-search sorting case-insensitive slices prefix-matching
1use std::cmp::Ordering;
2 
3pub struct PrefixIndex {
4 entries: Vec<String>,
5}
6 
7impl PrefixIndex {
8 pub fn new(mut entries: Vec<String>) -> Self {
9 entries.sort_by(|a, b| a.to_lowercase().cmp(&b.to_lowercase()));
10 Self { entries }
11 }
12 
13 pub fn search(&self, prefix: &str) -> &[String] {
14 let needle = prefix.to_lowercase();
15 
16 let start = self.entries.partition_point(|entry| {
17 entry.to_lowercase().as_str() < needle.as_str()
18 });
19 
20 let end = self.entries[start..].partition_point(|entry| {
21 starts_with_prefix(entry, &needle)
22 }) + start;
23 
24 &self.entries[start..end]
25 }
26 
27 pub fn contains(&self, value: &str) -> bool {
28 let needle = value.to_lowercase();
29 self.entries
30 .binary_search_by(|entry| entry.to_lowercase().cmp(&needle))
31 .is_ok()
32 }
33}
34 
35fn starts_with_prefix(entry: &str, prefix: &str) -> bool {
36 let lower = entry.to_lowercase();
37 match lower.as_str().cmp(prefix) {
38 Ordering::Less => false,
39 _ => lower.starts_with(prefix),
40 }
41}
01 / 01
STEP 01

Walkthrough

Space play ←→ step click any line
Three takeaways
  1. 1Keeping data sorted up front turns each query into a logarithmic binary search instead of a linear scan.
  2. 2partition_point finds the boundary where a predicate flips from true to false, letting you bracket a range with two calls.
  3. 3Normalizing case consistently on both storage and lookup keeps comparisons and prefix checks correct.

Related explainers

rust 
use std::cmp::Ordering;
use std::str::FromStr;
 
#[derive(Debug, Clone, PartialEq, Eq)]

Parsing and ordering semantic versions in Rust

parsing trait-implementation ordering
Intermediate 8 steps
rust 
use axum::{
    extract::State,
    routing::{get, post, MethodRouter},
    Json, Router,

Self-documenting routes in Axum

builder-pattern closures shared-state
Intermediate 8 steps
rust 
use std::collections::HashMap;
use std::fs::File;
use std::io::{self, BufRead, BufReader};
use std::path::Path;

Parsing INI files in Rust

parsing file-io hashmap
Intermediate 9 steps
rust 
use axum::{
    extract::{Path, Query},
    http::Uri,
    response::{IntoResponse, Redirect},

Building HTTP redirect handlers in Axum

redirects extractors url-handling
Intermediate 7 steps
rust 
use axum::{
    body::Body,
    extract::MatchedPath,
    http::{Request, StatusCode},

An admin route guard in Axum middleware

middleware authorization request-extensions
Intermediate 7 steps
rust 
use std::collections::VecDeque;
 
pub struct RollingAverage {
    window: VecDeque<f64>,

A rolling average over a sliding window

sliding-window running-sum ring-buffer
Intermediate 6 steps

Share this explainer

Here's the card — post it anywhere.

Prefix search with binary partitioning in Rust — share card
Made with highlit — turn any snippet into a walkthrough like this in about a minute.
Explain your code