O(n), a sorted one answers it in O(log n), and the whole point of last week was to earn that speed-up;(lo + hi) / 2 -- and the one-character discipline that kills it forever;std.sort.binarySearch, std.sort.lowerBound, std.sort.upperBound, std.sort.partitionPoint) and the compareFn / predicate shapes they expect;bsearch), Rust (binary_search, partition_point) and Go (sort.Search, slices.BinarySearch), and why the "where would it go?" answer matters more than the "is it there?" answer.fn (comptime T: type, items: []const T, ...) and works for any element type;lessThan idea we sorted with, because a search has to agree with the order the data was sorted in;Learn Zig Series):Last week I closed the sorting episode with a small confession: the whole reason we spend so much effort putting elements in order is so we can find them again in a hurry. An unsorted array can only answer "is this value here?" by looking at every element -- O(n), no shortcut exists, because any element you skipped could have been the one. Sort the array first and the same question collapses to O(log n): you look at the middle, decide which half your value must live in, throw the other half away, and repeat. A million elements searched in about twenty comparisons in stead of a million. That is one of the highest-leverage ideas in all of programming, and it looks so trivial that people underestimate exactly how many ways it bites -- the overflow, the off-by-one, the "not found" case, the difference between finding a match and finding the first match. Today we get every one of those right. But first -- the sorting debt from episode 116, all three exercises, in real compilable code ;-)
Exercise 1 -- prove your insertion sort is stable, and watch heapsort fail the same test. Stability means equal keys come out in the same relative order they went in. The clean way to test it is to sort a struct that carries its own original position, then check that within every run of equal keys those positions are still increasing. Here is insertion sort (unchanged from last week) plus the stability check, and the test passes:
const std = @import("std");
const Item = struct { key: u8, seq: usize };
fn insertionSort(comptime T: type, items: []T, lessThan: fn (T, T) bool) void {
var i: usize = 1;
while (i < items.len) : (i += 1) {
const key = items[i];
var j: usize = i;
while (j > 0 and lessThan(key, items[j - 1])) : (j -= 1) {
items[j] = items[j - 1];
}
items[j] = key;
}
}
fn byKey(a: Item, b: Item) bool {
return a.key < b.key;
}
fn isStable(items: []const Item) bool {
var i: usize = 1;
while (i < items.len) : (i += 1) {
// equal keys whose original positions went backwards == unstable
if (items[i].key == items[i - 1].key and items[i].seq < items[i - 1].seq) return false;
}
return true;
}
test "insertion sort keeps equal keys in original order" {
var xs = [_]Item{
.{ .key = 3, .seq = 0 }, .{ .key = 1, .seq = 1 }, .{ .key = 3, .seq = 2 },
.{ .key = 1, .seq = 3 }, .{ .key = 2, .seq = 4 }, .{ .key = 3, .seq = 5 },
};
insertionSort(Item, &xs, byKey);
try std.testing.expect(isStable(&xs));
}
Now the instructive half: run the same check against heapsort and it fails, because heapsort's whole mechanism is to swap the max element to the far end of the array, which happily jumps equal elements past one another. Feed it a slice of all-equal keys and the extraction phase reverses them:
fn siftDown(comptime T: type, items: []T, start: usize, lessThan: fn (T, T) bool) void {
var root = start;
while (true) {
var child = 2 * root + 1;
if (child >= items.len) break;
if (child + 1 < items.len and lessThan(items[child], items[child + 1])) child += 1;
if (!lessThan(items[root], items[child])) break;
std.mem.swap(T, &items[root], &items[child]);
root = child;
}
}
fn heapSort(comptime T: type, items: []T, lessThan: fn (T, T) bool) void {
if (items.len <= 1) return;
var start = items.len / 2;
while (start > 0) {
start -= 1;
siftDown(T, items, start, lessThan);
}
var end = items.len;
while (end > 1) {
end -= 1;
std.mem.swap(T, &items[0], &items[end]);
siftDown(T, items[0..end], 0, lessThan);
}
}
test "heapsort scrambles the order of equal keys" {
var xs = [_]Item{
.{ .key = 1, .seq = 0 }, .{ .key = 1, .seq = 1 }, .{ .key = 1, .seq = 2 },
.{ .key = 1, .seq = 3 }, .{ .key = 1, .seq = 4 },
};
heapSort(Item, &xs, byKey);
try std.testing.expect(!isStable(&xs)); // the point of the exercise: unstable, on purpose
}
Seeing the assertion flip from "stable" to "not stable" between two sorts that both produce a correctly-ordered array is the whole lesson: stability is a property of the algorithm, not of the output ordering. Both arrays are sorted by key; only one preserves the incoming order of ties.
Exercise 2 -- turn quicksort into introsort. Naive quicksort dies on already-sorted input: last-element pivots split off one element at a time, n levels deep, O(n^2). Introsort fixes this by counting recursion depth and bailing out to heapsort (guaranteed O(n log n)) once the depth exceeds 2 * log2(n). Small slices still go to insertion sort. The depth budget is the only new idea:
fn medianOfThree(comptime T: type, items: []T, lessThan: fn (T, T) bool) void {
const mid = items.len / 2;
const last = items.len - 1;
if (lessThan(items[mid], items[0])) std.mem.swap(T, &items[mid], &items[0]);
if (lessThan(items[last], items[0])) std.mem.swap(T, &items[last], &items[0]);
if (lessThan(items[last], items[mid])) std.mem.swap(T, &items[last], &items[mid]);
std.mem.swap(T, &items[mid], &items[last]); // park median at the pivot slot
}
fn introSort(comptime T: type, items: []T, lessThan: fn (T, T) bool) void {
const depth = 2 * std.math.log2_int(usize, @max(items.len, 1));
introSortImpl(T, items, lessThan, depth);
}
fn introSortImpl(comptime T: type, items: []T, lessThan: fn (T, T) bool, depth_limit: usize) void {
if (items.len <= 16) {
insertionSort(T, items, lessThan); // small slices: insertion wins
return;
}
if (depth_limit == 0) {
heapSort(T, items, lessThan); // the safety net: can never go quadratic
return;
}
medianOfThree(T, items, lessThan);
const pivot = items[items.len - 1];
var i: usize = 0;
var j: usize = 0;
while (j < items.len - 1) : (j += 1) {
if (lessThan(items[j], pivot)) {
std.mem.swap(T, &items[i], &items[j]);
i += 1;
}
}
std.mem.swap(T, &items[i], &items[items.len - 1]);
introSortImpl(T, items[0..i], lessThan, depth_limit - 1);
introSortImpl(T, items[i + 1 ..], lessThan, depth_limit - 1);
}
fn ascU32(a: u32, b: u32) bool {
return a < b;
}
test "introsort stays fast on the sorted-array worst case" {
const gpa = std.testing.allocator;
const n = 100_000;
const xs = try gpa.alloc(u32, n);
defer gpa.free(xs);
for (xs, 0..) |*v, k| v.* = @intCast(k); // already sorted -- the classic quadratic trap
introSort(u32, xs, ascU32);
var i: usize = 1;
while (i < xs.len) : (i += 1) try std.testing.expect(xs[i - 1] <= xs[i]);
}
Why can the fallback never make the bound worse? Because the depth budget is 2 * log2(n) levels of partitioning, each doing O(n) work across that level -- that is O(n log n) before any fallback -- and whatever slices remain when the budget hits zero are finished by heapsort, itself O(k log k) for a slice of size k. Sum the fallbacks and you are still bounded by O(n log n). The naive version would have taken minutes on that 100,000-element sorted array; introsort finishes it in a blink.
Exercise 3 -- sort indices, not elements. Sometimes you cannot (or do not want to) move the elements: they are huge and expensive to copy, or you need several different orderings of the same immutable data at once. The answer is an indirect sort -- allocate a []usize of indices 0, 1, 2, ... and sort those by looking through to the data. std.mem.sort takes a runtime context, so we pack the data slice and the comparator into it:
fn argsort(comptime T: type, gpa: std.mem.Allocator, items: []const T, lessThan: *const fn (T, T) bool) ![]usize {
const order = try gpa.alloc(usize, items.len);
for (order, 0..) |*slot, i| slot.* = i;
const Ctx = struct { items: []const T, less: *const fn (T, T) bool };
const cmp = struct {
fn f(ctx: Ctx, a: usize, b: usize) bool {
return ctx.less(ctx.items[a], ctx.items[b]); // compare by looking THROUGH the indices
}
}.f;
std.mem.sort(usize, order, Ctx{ .items = items, .less = lessThan }, cmp);
return order;
}
test "argsort orders indices without touching the data" {
const gpa = std.testing.allocator;
const data = [_]u32{ 40, 10, 30, 20 };
const order = try argsort(u32, gpa, &data, ascU32);
defer gpa.free(order);
try std.testing.expectEqualSlices(usize, &[_]usize{ 1, 3, 2, 0 }, order);
try std.testing.expectEqual(@as(u32, 40), data[0]); // data itself never moved
}
order now reads out the data in sorted order (data[order[0]] is the smallest) while data sits untouched. This exact pattern is how you sort a database result by three different columns without three copies of the rows, and it is the bridge into today's topic -- because an index sort produces exactly the kind of sorted key array that binary search lives on. Debt paid. On to searching ;-)
Binary search is four lines of logic wrapped around one landmine. The logic: keep a range [lo, hi) that could contain your target, look at the middle, and shrink the range to whichever half still could. The landmine is computing "the middle". The obvious mid = (lo + hi) / 2 is wrong on large inputs, because lo + hi can overflow the integer type before the division ever happens. This is not a hypothetical -- it was a real bug in java.util.Arrays.binarySearch that sat undetected in the JDK (and in Programming Pearls, the book that popularised the algorithm) for nearly twenty years. The fix is to compute the offset from lo in stead of the raw sum:
fn binarySearch(comptime T: type, items: []const T, target: T, lessThan: fn (T, T) bool) ?usize {
var lo: usize = 0;
var hi: usize = items.len; // half-open: hi is one PAST the last candidate
while (lo < hi) {
const mid = lo + (hi - lo) / 2; // never overflows -- (hi - lo) is always in range
if (lessThan(items[mid], target)) {
lo = mid + 1; // target is strictly right of mid
} else if (lessThan(target, items[mid])) {
hi = mid; // target is strictly left of mid
} else {
return mid; // items[mid] is neither less nor greater -> equal -> found
}
}
return null;
}
Two things deserve a stare. First, lo + (hi - lo) / 2 is arithmetically identical to (lo + hi) / 2 but (hi - lo) can never exceed the array length, so no overflow, ever. On a 64-bit usize and a real array you will not literally overflow, but the habit is free and it is correct, and correctness habits are how you avoid the bug that gets your name in a retrospective. Second, notice we never test equality with ==. We only ever call lessThan. "Not less, and not greater" is equality, expressed purely through the ordering the caller gave us -- which means this one function searches []u8, []f64, or a []Person sorted by age, without ever knowing what "equal" means for the type. Same mechanism-versus-policy split we sorted with last week.
This version answers one question: "is target present, and if so at what index?" It returns some matching index -- not necessarily the first -- and null when absent. That is often not enough, which is why the real workhorses are the two functions below.
Ninety percent of the time you do not want "is it here?", you want "where does it belong?". Lower bound is the first index whose element is not less than the target (the first spot where the target could be inserted while keeping the array sorted, ties landing before). Upper bound is the first index whose element is strictly greater than the target (insertion point with ties landing after). They differ by one line -- which side of the comparison the equal case falls on:
fn lowerBound(comptime T: type, items: []const T, target: T, lessThan: fn (T, T) bool) usize {
var lo: usize = 0;
var hi: usize = items.len;
while (lo < hi) {
const mid = lo + (hi - lo) / 2;
if (lessThan(items[mid], target)) lo = mid + 1 else hi = mid; // equal goes LEFT
}
return lo;
}
fn upperBound(comptime T: type, items: []const T, target: T, lessThan: fn (T, T) bool) usize {
var lo: usize = 0;
var hi: usize = items.len;
while (lo < hi) {
const mid = lo + (hi - lo) / 2;
if (lessThan(target, items[mid])) hi = mid else lo = mid + 1; // equal goes RIGHT
}
return lo;
}
Look at how little separates them. In lowerBound the test is "is items[mid] less than target?" -- if yes the answer is strictly right, otherwise (equal or greater) mid might be the answer so we keep it as the new hi. In upperBound the test flips to "is target less than items[mid]?" -- pushing the equal case into the lo = mid + 1 branch instead. That single asymmetry is the entire difference between "first element >= target" and "first element > target". Neither ever returns null: for an absent value both return the same index -- the gap where it would go -- which is frequently more useful than a bare "not found", because it tells you exactly where to insert.
Once you have both bounds, a whole family of queries falls out for free. The pair [lowerBound, upperBound) is exactly the half-open range of all elements equal to the target -- the "equal range". Its length is the count. lowerBound is the first occurrence; upperBound - 1 is the last (when the range is non-empty). And when lower equals upper, the element is absent and that shared index is where it belongs. One test exercises all of it:
fn ltU32(a: u32, b: u32) bool {
return a < b;
}
test "lower and upper bound bracket a run of equal keys" {
const xs = [_]u32{ 1, 3, 3, 3, 5, 8, 8, 13 };
const lo = lowerBound(u32, &xs, 3, ltU32);
const hi = upperBound(u32, &xs, 3, ltU32);
try std.testing.expectEqual(@as(usize, 1), lo); // first 3 sits at index 1
try std.testing.expectEqual(@as(usize, 4), hi); // one past the last 3
try std.testing.expectEqual(@as(usize, 3), hi - lo); // there are three 3s
// an ABSENT value: lower == upper == the insertion point
try std.testing.expectEqual(lowerBound(u32, &xs, 7, ltU32), upperBound(u32, &xs, 7, ltU32));
try std.testing.expectEqual(@as(usize, 5), lowerBound(u32, &xs, 7, ltU32)); // 7 slots before 8
}
Count how many times a value appears in a sorted array? upperBound - lowerBound. Find the first log entry newer than a timestamp? upperBound on the timestamp column. Find where a new record should be inserted to keep the array sorted? lowerBound. These are not different algorithms -- they are the same two functions read through different eyes. That is why I keep saying lower/upper bound are the ones to actually memorise; plain "found or not" is the special case you almost never want on its own.
Every off-by-one binary-search bug is a boundary-convention bug, and the cure is to commit to one invariant and never break it. Mine is the half-open range [lo, hi): the answer, if the loop has one, always lives in that window; lo is inclusive, hi is exclusive, and the window shrinks every iteration. Trace the guarantees:
lo = 0, hi = items.len -- the whole array, and hi is deliberately one past the last real index, which is why hi starts at len and not len - 1.lo < hi (a non-empty window). When lo == hi the window is empty and we stop.lo = mid + 1 (discard mid and everything left) or hi = mid (discard everything from mid rightward, but keep the possibility that mid itself is the answer). Because lo <= mid < hi always holds, the window strictly shrinks, so the loop must terminate -- in at most log2(n) + 1 steps.That last clause is the whole reason to be pedantic about conventions: if you accidentally write hi = mid - 1 in the lower-bound style, or start hi at len - 1, or loop on lo <= hi with an exclusive hi, you get an infinite loop, an out-of-bounds read, or a silently-wrong answer on the boundary elements. In safe Zig builds the out-of-bounds read at least traps at the exact line in stead of quietly returning garbage -- the same bounds-checking safety net we have leaned on all series -- but the right move is to not write the bug at all. Pick the half-open invariant, apply it identically to all three functions above, and the boundary cases take care of themselves. Nota bene: the empty array is handled with zero special-casing -- lo and hi both start at 0, lo < hi is immediately false, and every function returns 0 (or null for binarySearch), which is exactly right.
Here is where binary search stops being "a thing you do to arrays" and becomes a way of thinking. Strip it down and binary search really finds the flip point of a monotone predicate -- a yes/no question that is false, false, ..., false, true, true, ..., true with exactly one transition. Searching a sorted array is just the special case where the predicate is "is this element >= my target?". But the domain does not have to be an array at all; it can be a range of candidate answers:
fn firstTrue(n: usize, pred: fn (usize) bool) usize {
var lo: usize = 0;
var hi: usize = n;
while (lo < hi) {
const mid = lo + (hi - lo) / 2;
if (pred(mid)) hi = mid else lo = mid + 1; // find the first mid where pred flips true
}
return lo;
}
Same skeleton as lowerBound, with the array lookup replaced by a predicate call. Any question of the form "what is the smallest value that satisfies this monotone condition?" becomes a firstTrue. A classic worked example: integer square root -- the largest m with m*m <= x. The predicate "m*m > x" is monotone (once it is true it stays true), so isqrt is just the flip point minus one. The only wrinkle is that m*m can overflow a u64, so we rewrite the predicate as the algebraically-equivalent, overflow-proof m > x / m:
fn isqrt(x: u64) u64 {
if (x < 2) return x;
var lo: u64 = 1;
var hi: u64 = x; // for x >= 2, m == x is always too big, so the answer is below x
while (lo < hi) {
const mid = lo + (hi - lo) / 2;
// (mid > x / mid) is EXACTLY (mid*mid > x) for mid >= 1 -- but without the overflow
if (mid > x / mid) hi = mid else lo = mid + 1;
}
return lo - 1; // last mid whose square still fits under x
}
test "integer sqrt via binary search on the answer" {
try std.testing.expectEqual(@as(u64, 0), isqrt(0));
try std.testing.expectEqual(@as(u64, 3), isqrt(15)); // 3*3=9 <= 15 < 16
try std.testing.expectEqual(@as(u64, 4), isqrt(16));
try std.testing.expectEqual(@as(u64, 1000), isqrt(1_000_000));
try std.testing.expectEqual(@as(u64, 4_000_000_000), isqrt(16_000_000_000_000_000_000)); // no overflow
}
That last assertion squares a four-billion answer against a number near the top of u64 and still lands exactly right, because the m > x / m phrasing never multiplies. This "binary search on the answer" pattern is worth its weight in gold: minimum machine capacity to finish a job by a deadline, smallest buffer size that fits a workload, the tightest threshold that still passes a check -- all of them are firstTrue over a predicate you can evaluate but not invert. Whenever a problem says "find the smallest/largest X such that some checkable condition holds", reach for bisection before you reach for anything clever.
As with sorting, you should reach for the stdlib first and only hand-roll when you have a reason. Zig's std.sort module gives you the whole family, all taking a context and a comptime comparison function. std.sort.binarySearch returns ?usize; lowerBound and upperBound return the insertion indices we built by hand; and partitionPoint is the raw firstTrue-over-a-predicate primitive. The comparators here return a three-way std.math.Order rather than a bool, which lets binarySearch distinguish less / equal / greater in one call:
fn orderU32(key: u32, item: u32) std.math.Order {
return std.math.order(key, item);
}
test "the stdlib binary-search family" {
const xs = [_]u32{ 1, 3, 3, 3, 5, 8, 8, 13 };
try std.testing.expectEqual(@as(usize, 1), std.sort.lowerBound(u32, &xs, @as(u32, 3), orderU32));
try std.testing.expectEqual(@as(usize, 4), std.sort.upperBound(u32, &xs, @as(u32, 3), orderU32));
try std.testing.expect(std.sort.binarySearch(u32, &xs, @as(u32, 8), orderU32) != null);
try std.testing.expectEqual(@as(?usize, null), std.sort.binarySearch(u32, &xs, @as(u32, 7), orderU32));
// partitionPoint == firstTrue: first index whose element is NOT less than 5
const pp = std.sort.partitionPoint(u32, &xs, {}, struct {
fn pred(_: void, item: u32) bool {
return item < 5;
}
}.pred);
try std.testing.expectEqual(@as(usize, 4), pp);
}
Notice partitionPoint takes a predicate that says "is this element still in the left (false) part?", and returns the first index where that predicate becomes false -- which is precisely the boundary firstTrue computes. That is the same primitive our isqrt was built on, handed to you tuned and tested. The one thing to keep straight is the argument annotation: I wrote @as(u32, 3) in stead of a bare 3, because the key's type has to match the element type the comparator expects -- pass a bare integer literal and the compiler infers comptime_int and rejects the mismatch, which is Zig catching a type error you would have hit at runtime in a weaker language.
Hand-picked test arrays let bugs survive; the boundary conditions in binary search are exactly where the three-example test is weakest. So we do what we did for sorting -- property-based testing against a trusted oracle. The oracle here is dead simple and obviously correct: a linear scan. For a random sorted array and a random key, the number of elements strictly less than the key is the lower bound, and the number less-than-or-equal is the upper bound. If our O(log n) search disagrees with the O(n) scan even once across hundreds of random rounds, we have a bug:
test "hand-written search agrees with a linear scan on random data" {
var prng = std.Random.DefaultPrng.init(0xC0FFEE);
const rand = prng.random();
const gpa = std.testing.allocator;
var round: usize = 0;
while (round < 300) : (round += 1) {
const n = rand.intRangeAtMost(usize, 0, 200); // includes 0 and 1 -- the crash sizes
const xs = try gpa.alloc(u32, n);
defer gpa.free(xs);
for (xs) |*v| v.* = rand.int(u32) % 50; // small range -> lots of duplicates
std.mem.sort(u32, xs, {}, std.sort.asc(u32));
const key = rand.int(u32) % 50;
var lt: usize = 0; // elements strictly less than key
var le: usize = 0; // elements less than or equal to key
for (xs) |v| {
if (v < key) lt += 1;
if (v <= key) le += 1;
}
try std.testing.expectEqual(lt, lowerBound(u32, xs, key, ltU32));
try std.testing.expectEqual(le, upperBound(u32, xs, key, ltU32));
try std.testing.expectEqual(le > lt, binarySearch(u32, xs, key, ltU32) != null);
if (binarySearch(u32, xs, key, ltU32)) |idx| try std.testing.expectEqual(key, xs[idx]);
}
}
I actually run this -- 300 rounds, sizes from 0 to 200, keys mod 50 so most searches hit dense runs of duplicates and both the "present" and "absent" paths get hammered. Two details are load-bearing. The size range includes 0 and 1, because empty and single-element arrays are where naive searches go wrong (an empty array must return 0/null, not read items[0]). And the "present" check is le > lt -- the key exists exactly when at least one element equals it, i.e. when the less-or-equal count exceeds the strictly-less count. Because everything runs on std.testing.allocator, a leaked buffer fails the test outright, the same guard-rail that carried us through the whole allocator arc.
In C, the tool is bsearch(key, base, count, size, compare) from <stdlib.h>, and it inherits every C tradeoff. The comparator takes two const void* you cast by hand, the elements are shuffled as raw bytes, and -- the real limitation -- it returns a pointer to a matching element or NULL. That is the weak "found / not found" answer with no notion of where a missing key belongs, so C programmers who need an insertion point end up writing the loop by hand anyway. No lower bound, no upper bound, no equal range: bsearch gives you the least useful of the questions.
In Rust, the standard library gets the design right. slice::binary_search returns a Result<usize, usize> -- Ok(index) when found, and crucially Err(insertion_point) when not, so the "where would it go?" answer is baked into the type. There is binary_search_by and binary_search_by_key for custom orderings, and slice::partition_point is the exact firstTrue predicate primitive we built. Rust's Result here is a small masterclass: the absent case is not an error you shrug at, it is a value carrying the insertion index, which is almost always what you actually needed.
In Go, the idiomatic tool is the predicate form directly: sort.Search(n, func(i int) bool { ... }) returns the smallest index in [0, n) for which the function is true -- Go decided the general "binary search on a monotone predicate" is the primitive, and specialising it to array lookup is your one-line closure. The newer generics-based slices.BinarySearch(s, target) returns (index, found), the same insertion-point-plus-flag Rust exposes. Go's philosophy shows through: one small, obvious primitive in the standard library, and you compose the specific search you need on top of it.
Our Zig versions sit exactly where Zig always sits: the whole family is a couple dozen readable lines, the comparator is an inlined comptime value with zero call overhead, the element type flows through the generics so a mismatched key is a compile error, and the half-open invariant is the same in every one so the boundary cases are handled once and reused. Same idea in four languages -- but here you can see all the way down to the mid computation and know precisely why the overflow can never happen ;-)
Rotated-array search. A sorted array that has been rotated by some unknown amount (e.g. [5, 8, 13, 1, 3, 3]) is no longer globally sorted, but each half still is -- which is enough for binary search if you are careful. Write a searchRotated(comptime T, items, target, lessThan) ?usize that finds target in O(log n) by, at each step, working out which half is the sorted one and whether the target lies inside it. Test it against a linear scan on random rotations, including a rotation of 0 (a plain sorted array).
Peak finding without a sorted array. Given a slice where no two adjacent elements are equal, a "peak" is any element greater than both its neighbours (the ends count with an imaginary -infinity just past them). Write findPeak(comptime T, items, lessThan) usize that returns the index of a peak in O(log n) -- the trick is that the predicate "is items[mid] on an upward slope toward a peak?" is monotone even though the array is not sorted. This shows binary search working on structure that is not a total order.
Interpolation search, and when it beats binary search. For uniformly distributed numeric keys you can guess the probe position from the key's value in stead of always halving -- mid = lo + (target - items[lo]) * (hi - lo) / (items[hi] - items[lo]). Implement it for []u64, guard every division against a zero denominator, and benchmark it against your binarySearch on (a) a uniformly-random sorted array and (b) an exponentially-skewed one. Explain why interpolation search is O(log log n) on the first and can degrade to O(n) on the second, and argue why the boring binary search is still the right default.
Everything today rested on one assumption we never questioned: that the data lives on a line. Sorted, totally ordered, "left half or right half" -- binary search only works because every element has a well-defined position relative to every other, and that lets us throw away half the world with a single comparison. But an enormous amount of the most interesting data has no such line through it. Cities are not "less than" or "greater than" each other -- they are connected by roads, in a web where the only questions that make sense are "what is adjacent to this?" and "can I get from here to there?". People, dependencies, web pages, network routers, molecules -- all of them are relationships, not rankings. To model that we need a structure built from nodes and the edges between them, and searching it means something completely different from halving a range. Sorting and searching a line was the warm-up. The web of connections is where we go next ;-)
Thanks for reading, and tot de volgende keer!
@scipio