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 serde::Deserialize;
 
#[derive(Debug, Deserialize)]
#[serde(untagged)]

Parsing flexible JSON shapes with serde

deserialization enums json
Intermediate 6 steps
rust 
use std::cmp::{Ordering, Reverse};
use std::collections::BinaryHeap;
use std::fs::File;
use std::io::{self, BufRead, BufReader, BufWriter, Lines, Write};

K-way merge of sorted logs in Rust

binary-heap k-way-merge streaming-io
Intermediate 8 steps
rust 
use axum::{
    extract::{Path, State},
    response::sse::{Event, KeepAlive, Sse},
};

Streaming import progress with SSE in Axum

server-sent-events streams watch-channel
Advanced 7 steps
rust 
use std::f64::consts::PI;
 
#[derive(Debug, Clone, Copy)]
pub struct LatLng {

Building geographic bounding boxes in Rust

geospatial value-types option
Intermediate 7 steps
rust 
use chrono::{Duration, NaiveDate};
 
#[derive(Debug)]
pub struct DateRange {

Parsing and iterating date ranges in Rust

error-handling iterators parsing
Intermediate 7 steps
rust 
use std::collections::VecDeque;
use std::sync::{Arc, Condvar, Mutex};
use std::time::{Duration, Instant};
 

Building a counting semaphore in Rust

concurrency synchronization condition-variable
Advanced 9 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