java 36 lines · 9 steps

Prefix search with binary search bounds

A sorted word array lets you find every entry sharing a prefix by locating two binary-search boundaries.

Explained by highlit
Intermediate binary-search sorting range-query immutability
1public final class PrefixSearch {
2 
3 private final String[] words;
4 
5 public PrefixSearch(String[] words) {
6 this.words = words.clone();
7 for (int i = 0; i < this.words.length; i++) {
8 this.words[i] = this.words[i].toLowerCase();
9 }
10 Arrays.sort(this.words);
11 }
12 
13 public List<String> withPrefix(String prefix) {
14 String needle = prefix.toLowerCase();
15 int from = lowerBound(needle);
16 int to = lowerBound(needle + Character.MAX_VALUE);
17 if (from >= to) {
18 return List.of();
19 }
20 return List.of(Arrays.copyOfRange(words, from, to));
21 }
22 
23 private int lowerBound(String key) {
24 int lo = 0;
25 int hi = words.length;
26 while (lo < hi) {
27 int mid = (lo + hi) >>> 1;
28 if (words[mid].compareTo(key) < 0) {
29 lo = mid + 1;
30 } else {
31 hi = mid;
32 }
33 }
34 return lo;
35 }
36}
01 / 01
STEP 01

Walkthrough

Space play ←→ step click any line
Three takeaways
  1. 1Sorting once up front turns every prefix query into two logarithmic lookups.
  2. 2A lower-bound binary search is a reusable primitive for finding both ends of a range.
  3. 3Appending the maximum char value neatly marks the exclusive end of a prefix range.

Related explainers

java 
@Component
@Converter
public class EncryptedStringConverter implements AttributeConverter<String, String> {
 

Transparent column encryption in Spring & JPA

encryption aes-gcm jpa-converter
Advanced 10 steps
java 
package com.acme.billing.config;
 
import org.springframework.boot.autoconfigure.condition.ConditionalOnProperty;
import org.springframework.boot.context.properties.ConfigurationProperties;

Feature-flagged beans with Spring @ConditionalOnProperty

feature-flags conditional-beans strategy-pattern
Intermediate 5 steps
java 
public static Map<String, String> parseCookieHeader(String header) {
    Map<String, String> cookies = new LinkedHashMap<>();
    if (header == null || header.isBlank()) {
        return cookies;

Parsing an HTTP Cookie header in Java

string-parsing http url-decoding
Intermediate 6 steps
go 
package logging
 
import (
	"context"

Deduplicating log attributes in Go's slog

decorator-pattern structured-logging immutability
Intermediate 8 steps
java 
public class TimedSocketReader {
 
    private static final int READ_TIMEOUT_MS = 5_000;
    private static final int CONNECT_TIMEOUT_MS = 3_000;

Reading a socket with connect and read timeouts

sockets timeouts io
Intermediate 8 steps
python 
import re
from functools import total_ordering
from typing import Optional
 

Parsing and comparing semantic versions

regex operator-overloading sorting
Intermediate 7 steps

Share this explainer

Here's the card — post it anywhere.

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