Dive C4.03.3

Searching

An unordered sequence answers "where is 20?" by checking everything. A sorted one answers it by halving.

This is the second half of the sorting bargain. Linear search walks a sequence from the front, comparing each element — O(n), and it needs no order. Binary search starts in the middle of a sorted sequence and discards the half that cannot hold the target each step — O(log n) — but only if it can reach the middle in one step, which means an array, not a singly-linked list. The same O(log n) is what an F# Set and Map give, because each is a balanced tree. This dive writes all three in F#, verified in dotnet fsi, and closes the module on how the bus finds work: a job by its id, and the due jobs by their run time.

Find 20, two ways Module hub

C4.03.3 · part 1

Linear search — O(n) over anything

The simplest search walks the list and stops at the first element that matches, returning its index. It works on any list, in any order, and touches up to every element — O(n). In F# it is a three-clause recursion: an empty list returns None; a head that matches returns Some the current index; otherwise advance.

// linear search: first index whose element satisfies pred
let rec linear pred i lst =
    match lst with
    | [] -> None
    | x :: _ when pred x -> Some i
    | _ :: t -> linear pred (i + 1) t

// val linear : pred:('a -> bool) -> i:int -> lst:'a list -> int option

linear (fun x -> x = 20) 0 [5; 8; 10; 12; 20; 30; 42]
// val it : int option = Some 4

linear (fun x -> x = 99) 0 [5; 8; 10; 12; 20; 30; 42]
// val it : int option = None

int option: the result type: Some i for a hit, None for a miss — the typed, total alternative to a sentinel like -1.
when pred x: a guard on the match clause: the head matches only if the predicate holds. The clause order makes the empty case and the hit case unambiguous.
O(n): worst case touches every element, so a single search of an unsorted sequence costs no more than a scan — but no less, either.

C4.03.3 · part 2

Binary search — O(log n) over a sorted array

If the sequence is sorted and indexable, each comparison can discard half of what remains. Probe the middle: if it equals the target, done; if it is too small, search the right half; if too large, the left. The bounds close in until they cross. In F# this wants an array — indexing arr.[mid] is O(1) on a CLR array — and is a tail recursion over the lo / hi window.

// binary search over a sorted array (random access is O(1))
let binarySearch (arr: int[]) target =
    let rec go lo hi =
        if lo > hi then None
        else
            let mid = (lo + hi) / 2
            if arr.[mid] = target then Some mid
            elif arr.[mid] < target then go (mid + 1) hi
            else go lo (mid - 1)
    go 0 (arr.Length - 1)

// val binarySearch : arr:int[] -> target:int -> int option

let arr = [| 5; 8; 10; 12; 20; 30; 42 |]
binarySearch arr 20
// val it : int option = Some 4   ·  probed 12, then 30, then 20
binarySearch arr 99
// val it : int option = None

Binary search over a list is a trap: reaching the middle of a singly-linked list is itself an O(n) walk, so "binary search" over a list is O(n log n) — slower than a plain scan. Sorted data you intend to search lives in an array, exactly as the Elixir version wants a tuple, not a list.

Two ways to find 20

Over the sorted sequence [5; 8; 10; 12; 20; 30; 42], linear search walks from the left and reaches 20 at index 4 in five comparisons; binary search probes 12, then 30, then 20 in three. Select a strategy: the diagram marks the elements each one touches, and the readout names the probes and the cost. Both return Some 4 — the difference is how many comparisons it took.

find 20 · select a strategy

cost: O(n) · probes elements one by one — 5 here

result: Some 4

Both find 20; binary search asks sharper questions. Each comparison it makes discards half of what remains, so it needs about log₂ n of them — three for seven elements, twenty for a million.

C4.03.3 · part 3

The same O(log n) in a Set and a Map

Binary search is the descent of a balanced tree flattened onto an array. F# gives that descent directly: Set and Map are immutable balanced trees, so Set.contains and Map.tryFind are O(log n) — the same as binary search, but with cheap insertion too, since adding an element shares most of the existing tree rather than rewriting an array. This is the structure the next module, C4.04, takes apart in full; here it is the bridge from "search a sorted array" to "look up a key".

let s = Set.ofList [5; 8; 10; 12; 20; 30; 42]
Set.contains 20 s     // val it : bool = true     · O(log n)
Set.contains 99 s     // val it : bool = false

let m = Map.ofList [("JOB0000000001", 100L); ("JOB0000000002", 250L)]
Map.tryFind "JOB0000000002" m
// val it : int64 option = Some 250L   ·  O(log n) keyed lookup

Binary search

O(log n) over a sorted array, but each update rewrites the array — costly to keep current.

Set / Map

O(log n) lookup and O(log n) insert, with structural sharing — the structure a live queue is built on.

C4.03.3 · the bus

EchoMQ in F#

Status — echo_fs is an in-memory model. The EchoMQ protocol — the Lua transitions executing on a Valkey wire — is not implemented (there is no Lua and no Valkey client in the code); that is the coming-soon transport (EchoMQ.Connector). This block shows how the model uses the structure, not a running bus.

The bus searches in two shapes, and both are this dive. To look up a single job it keys into the Rows map — a Map.tryFind, O(log n), the keyed search above. To decide which scheduled jobs are ready to run, it asks a range question: which parked jobs have a due-time at or before now. That is a search by score — the range query a sorted-by-time index answers, the analog of Valkey's ZRANGEBYSCORE.

EchoMQ in F#

Finding due jobs by their run time

Quoted from echo_fs/EchoMQ/Store.fs: Schedule is a Map<string, int64> from a job id to its due-at millisecond. The promote pump filters that map for the entries due at or before now and moves them back to pending — a search by score over the schedule. The lease reaper does the same shape over Active, keyed on the lease deadline.

// echo_fs/EchoMQ/Store.fs — id -> due-at (ms): jobs parked until run-at
Schedule: Map<string, int64>

// promote: which scheduled jobs are due at or before now?
let due =
    st.Schedule
    |> Map.filter (fun _ dueAt -> dueAt <= now)
    |> Map.toList
    |> List.map fst

So the queue's two finds are this module's two searches: a keyed lookup for one job (O(log n) into Rows), and a range query for the due jobs (a scan-by-score over Schedule) — the ZRANGEBYSCORE the Valkey transport will push to the server.

Status. The in-memory Store.promote and Store.reap run these scans today, and EchoMQ.Tests covers them. The Valkey transport (EchoMQ.Connector) replaces the host-side Map.filter with a server-side range query when it lands; the wire is the coming-soon part.

Sort once, search many — and the comparison floor

Sorting is an investment. To search a sequence once, a linear scan at O(n) beats paying n log n to sort it first. To search it many times, sorting once and then binary searching — or holding it in a Set — wins quickly; the break-even is a handful of lookups. That same logic, in C4.04, picks a map: a hash pays once up front to make every lookup O(1) on average, no ordering required.

There is a hard limit on the sorting half. Any sort that works only by comparing pairs is, in effect, walking a decision tree whose leaves are the n! possible orderings; a binary tree with that many leaves is at least log₂(n!) ≈ n log n deep. So no comparison sort beats n log n in the worst case — merge sort meets that floor, and only sorts that exploit the keys (counting, radix) can go lower. The bus sidesteps the whole question by never re-sorting: its Set holds a total order at all times.

// one sort, then many fast searches
let sorted = List.sort data       // O(n log n), once
binarySearch (List.toArray sorted) 20  // O(log n), each lookup

// comparison-sort floor:  log2(n!) ~ n log n  (no comparison sort beats it)

Elixir / F4.03 · sort, then halve

Pay n log n once; binary search wants a tuple, where elem/2 is O(1).

F# / C4.03 · the same, statically typed

Binary search wants an array; a Set / Map gives ordered O(log n) lookup with cheap inserts — the bus's choice.

That closes the module. Next module: C4.04 — Maps, sets & hashing, where a hash trades ordering for average-O(1) lookup — and where the bus's Rows map gets its full treatment.

References

Sources

FSharp.Core API reference — the Array, List, Set, and Map modules.
Microsoft — F# documentation — arrays, recursion, and the F# collection types.
Microsoft — .NET documentation — the CLR array and O(1) indexing.
The F# Software Foundation — F# on the .NET runtime.

Related in this course

Elixir — F4.03.2 · Linear & binary search — the same two searches, the E4 sibling.
C4 — Algorithms & Data Structures — the chapter this dive sits in.
C1.07 — Collections — the F# array, Set, and Map this dive searches.
C4.03.1 — Merge sort · C4.03.2 — Quicksort