skip to content

How does sort.Search work over an index space, and what must its predicate guarantee?

level: seniorimportance: nice to knowfreq 26%

answer

  1. it is handed a count, not a container
  2. smallest index where the answer flips
  3. false prefix, then true forever
  4. the miss result is n, not -1
  5. each probe may cost a disk read

basics

~20 s

sort.Search(n, f) returns the smallest index i in the range 0 to n-1 where f(i) is true, and returns n when none is. The predicate must be false for a prefix of that range and true for the rest.

solid answer

~50 s

`sort.Search(n int, f func(int) bool) int` searches an **index space**, not a slice: give it a count and a predicate, and it returns the smallest `i` in `[0, n)` where `f(i)` is true, or `n` if the predicate never is. The contract on `f` is monotonicity - false for a possibly empty prefix, then true for the remainder - since that is what binary search halves on. Because only an integer is handed to `f`, the elements need never be in memory: a CLI answering lookups against a local on-disk index can search fixed-width records by seeking to record `i` inside the predicate, spending about log2(n) reads instead of a scan. Write the predicate as "key at i is at or after the target", then check `i < n && key(i) == target` to turn that lower bound into found or not-found.

code

go · 7 lines
go
// keyAt seeks to the fixed-width record at index i and returns its key.
i := sort.Search(n, func(i int) bool {
	return keyAt(i) >= target
})
if i < n && keyAt(i) == target {
	// record i is the match; about log2(n) reads got us here
}

go deeper

for a junior

Know the shape: you pass a count and a function over indices, and you get back the first index where that function is true, or the count itself when it never is.

for a middle

Explain the monotonicity requirement and why the predicate is written with a >= comparison rather than an equality, then show the follow-up check that turns a lower bound into found or not-found.

for a senior

Demonstrate the use it exists for: searching something that is not in memory, where each of the roughly log2(n) predicate calls is a read, and the optimisation target is the cost of a single probe.

for a principal

Judge whether the abstraction is worth it: a hand-written predicate over an index space is powerful and easy to get subtly wrong, so decide when a plain sorted slice, or a real index structure, is the safer thing for a team to maintain.

## The signature is the whole idea ```go func Search(n int, f func(int) bool) int ``` No slice. No element type. No comparison between two values. `sort.Search` is handed the **size of an index space** and a predicate over the indices in it, and it returns the smallest index at which the predicate holds - `n` if it never does. That is a deliberately more abstract interface than `slices.BinarySearch`, and the abstraction is what buys you things a slice-based search cannot do. ## The contract on the predicate `f` must be **monotone** over `[0, n)`: false for some (possibly empty) prefix, then true for the (possibly empty) remainder. Equivalently, `f(i) == true` must imply `f(i+1) == true`. Under that assumption the search can halve: if `f(mid)` is true, the answer is at `mid` or earlier; if false, it is after `mid`. If your predicate is not monotone - true, false, true across the range - `sort.Search` returns *some* index, chosen by whichever path the halving took. It is not an error and there is no panic; it is simply not the answer to any question you asked. Monotonicity is the same class of promise that sortedness is for a slice search, and the same discipline applies: establish it where the data is built, and assert it in tests. ## Turning it into a key lookup The idiomatic shape is a lower bound followed by an equality check: ```go i := sort.Search(n, func(i int) bool { return keyAt(i) >= target }) if i < n && keyAt(i) == target { // found at position i } ``` `>=` is what makes the predicate monotone over ascending keys: once a key is at or past the target, every later key is too. The result is the first position not before the target - a lower bound - which is exactly the insertion point semantics you get from the slices search. The second line is not optional: `sort.Search` alone never says "found", only "here is where it would start", and `i` can legitimately equal `n`, in which case indexing would panic. Swapping `>=` for `>` gives the upper bound instead, and the two together delimit a run of equal keys - the standard way to answer "how many records have this key" over sorted data. ## Why the index space matters Because `f` receives only an integer, the thing being searched need not be a Go slice at all: - **Records on disk.** A local index file of fixed-width records lets you compute the byte offset of record `i` arithmetically. The predicate seeks and reads one record; the search touches about log2(n) of them. A million-record file becomes roughly twenty reads instead of a full scan, with nothing loaded into memory. - **A remote or paged store.** Anything addressable by ordinal works the same way, and the predicate is where you put the caching so a repeated probe does not repeat the I/O. - **A computed answer space.** The "array" can be virtual: search `[0, n)` for the smallest buffer size, worker count or threshold whose measured cost meets a budget. The predicate evaluates a monotone function rather than reading data. ## The cost model, and where it bites The search calls `f` about ceil(log2(n)) times, and **the cost of the search is the cost of the predicate**. That inverts the usual intuition: with an in-memory slice, twenty comparisons are free and nobody thinks about them; with one disk read or one network round trip per call, twenty probes is the entire latency budget of the operation. Making the predicate cheap - a tight read, a cached page, a decoded key rather than a decoded record - is the optimisation that matters, not the search itself. ## When to reach for it rather than the slices search Use `slices.BinarySearch` or `slices.BinarySearchFunc` whenever the data is already a sorted slice in memory: they are shorter, type-safe, and return the found flag for you. Reach for `sort.Search` when there is no slice to hand it - data behind an accessor, elements too large or too many to materialise, an answer space rather than a container, or a search over parallel arrays where the key lives in one and the payload in another. The convenience wrappers `sort.SearchInts`, `sort.SearchStrings` and `sort.SearchFloat64s` remain in the standard library for slices of those types, but new code with a slice in hand should prefer the generic `slices` functions.

  • What does sort.Search return when the predicate is false for every index in the range?
    It returns n - the length of the index space, one past the last valid index. That is the same convention as a slice search's insertion point: it is a position, not an index, so any code that then reads element i must check `i < n` first. The lookup idiom `if i < n && keyAt(i) == target` exists precisely to handle that case and the not-equal case together.
  • How many times is the predicate called, and why does that matter more than usual here?
    About ceil(log2(n)) times - roughly twenty for a million entries. Over an in-memory slice those calls are free, but over an on-disk or remote index each call is a read, so the predicate's cost is the operation's latency. That is why the work worth doing is making a probe cheap: decode only the key, cache a fetched page, avoid re-reading the same record on the confirming equality check.
  • Why is the predicate normally written with >= rather than ==?
    Equality is not monotone: it is false, then true at one point, then false again, so binary search cannot halve on it. `keyAt(i) >= target` flips exactly once over ascending keys, satisfying the false-prefix-then-true contract, and yields the first position at or after the target. The equality check afterwards converts that lower bound into a found or not-found answer.
  • When would you use sort.Search even though the data is a sorted slice in memory?
    When the key is not the element: parallel arrays where the ordering key lives in one slice and the payload in another, or a slice of large structs where the predicate should touch only one field. It is also the tool for an answer space that is not data at all - the smallest worker count or buffer size whose cost meets a budget - since the predicate can compute rather than read.

Guessing a page number in a dictionary by asking only "is the word I want at or after this page?". You never hold the whole book in your hands; you just open at a page number and answer yes or no.

saying these in an interview costs you the question

  • Thinks sort.Search returns -1 when nothing matches
  • Uses an equality predicate, which is not monotone
  • Treats the returned index as a confirmed match without checking the key
  • Indexes at the returned position without checking i < n
  • Assumes it needs a slice to search