Binary search isn't about search II. Loop invariant of leftmost element search

In the first “Binary search isn’t about search” post, we spoke about using assert statements to enforce your loop invariants. Our plain old everyday binary search invariant can be summarized as such: For all x in L[0:l]1, x is strictly less than T, the element we are searching for. For all y in L[r:len(L)]2, y is strictly greater than T, the element we are searching for. Or, if we want to be even terser, we could note this as simply...

March 8, 2025

Check my math - NixOS vs the Most Complicated Program on Earth (MCPOE)

Imagine you had the Most Complicated Program On Earth (MCPOE), with 1,000,000 dependencies. Every dependency must be build correctly exactly right or the MCPOE will fail to compile. MCPOE’s 10x dev team chose their packages so that each dependency has only a 1/1,000,000 chance of having something go wrong when you’re installing them - maybe a whitespace character snuck into the wrong build script, maybe solar wind hit the build computer....

April 14, 2024

Most 2 digit numbers not divisible by 2, 3, or 5 are prime

There are only four single-digit primes: 2, 3, 5, and 7. So all two-digit numbers are either prime, or divisible by one of these four numbers. Of the four, 2, 3 and 5 are all very easy to spot check whether a number is divisible by them or not (for 3, add the digits first, and see if that sum is divisible by 3). If a given 2-digit number doesn’t fall into this category, 7 times out of 8, it’s prime....

December 4, 2023