DEV Community: Sadanand Dodawadakar

Binary Search is NOT About Searching

Sadanand Dodawadakar — Sat, 20 Jun 2026 02:37:35 +0000

Every one of us learned binary search the same way. We have a sorted array. Want to find a specific value x in it. We compare x to the middle element, throw away half the array, and repeat. O(log n). Done. The textbook gives you the algorithm, We implement it once or twice, and from that point on we reach for it whenever the words "sorted array" appear.

This is correct, but it is the least interesting thing binary search does.

The deeper truth — the one most courses skip — is that binary search isn't really about searching at all. It is a technique for inverting any monotonic predicate. The sorted-array case happens to be one instance of this, and a rather a boring one. The interesting instances are problems that don't look like search problems at all: how many days to ship?, what eating speed is fast enough?, what is the median of two arrays?, what is √2 to six decimal places? All of these are binary search problems, and none of them have a sorted array in sight.

This article is about getting from the boring case to the interesting ones — and watching the framework do the lifting along the way.

1. The Problem

You have a sorted array of n integers, A. You have a target value x. Return the index i such that A[i] == x, or report that no such index exists.

A small concrete example. Let A = [1, 4, 7, 11, 13, 18, 22, 30] and x = 13. The answer is i = 4.

This is the kind of problem every textbook uses. It is what people mean when they say "binary search." Most programmers can implement it from memory: maintain two pointers lo and hi, look at the middle element, throw away the half that can't contain x, repeat. After at most ⌈log₂(n)⌉ iterations the search space is empty, and we either found x or we didn't.

This version of the problem is so familiar that it's worth pausing to notice something subtle: how little of the problem statement we are actually using. The array is "sorted." That's it. We do not use the array's data type, the gaps between elements, the size of the integers, the fact that they happen to live in a contiguous block of memory. We use one structural fact — sortedness — and discard the rest.

Three iterations to find x = 13 in an 8-element array. The midpoint comparison eliminates half the array each time. Correct, fast, and — as the rest of this article will argue — the least interesting use of the technique.

As we'll see in Section 5, how we will apply binary search, when we don't even use sortedness in the way you'd expect.

2. What We Observe

Before any algorithm, look at the input.

The array is sorted. State this more precisely: it is monotonically non-decreasing. For any two indices i < j, we have A[i] ≤ A[j]. This is a richer statement than "sorted" because it tells us something specific about a predicate defined on the array.

Define the predicate P(i) = (A[i] ≥ x). Because the array is monotonically non-decreasing, this predicate is monotonic on the index i: once it becomes true at some index, it stays true for all larger indices. There is some critical index — call it the boundary — where P transitions from false to true. For our example array and x = 13:

i:     0   1   2   3   4   5   6   7
A[i]:  1   4   7   11  13  18  22  30
P(i):  F   F   F   F   T   T   T   T
                       ↑
                    boundary

If we can find this boundary, we have solved the original problem: index 4 is where P first becomes true, and that index either contains x or proves x is absent.

P(i) = (A[i] ≥ 13) rendered as a strip beneath. The values are just one way to produce the F → T transition; what binary search actually consumes is the transition itself.

Here is the third and important observation, and the one that will eventually break the article open: the only thing about a "sorted array" that binary search actually uses is that some predicate is monotonic over its indices. Not the values. Not the gaps. Not even the array. Just the monotonicity. Everything else is incidental to a problem that happens to be conveniently shaped.

3. How We Decompose

Let's restate binary search as a composition of two parts.

Part one is the predicate: a function that, given a candidate index (or candidate value, in the more general case), tells you whether the boundary lies to its left or its right. In the textbook problem, the predicate is P(i) = (A[i] ≥ x). It is monotonic — that's the structural fact we observed — and it is cheap to evaluate (one comparison, O(1)).

Part two is the halving loop: keep two pointers lo and hi bracketing the boundary, evaluate the predicate at the midpoint, discard the half that can't contain the boundary. This is the part most courses focus on, and it's the part that's the same in every binary search anyone has ever written. There is nothing to think about in the loop.

The thinking is in the predicate.

The article has a thesis-in-miniature that's worth repeating because it will come up several more times before we finish: the predicate is the thinking. The loop is the typing.

What does this decomposition buy us? It lets us notice that the structure of binary search has nothing inherently to do with arrays. We picked an array because it's a convenient shape — indices are integers, midpoints are easy, comparisons are cheap. None of those properties are intrinsic to binary search itself. As we'll see, the same loop works on integer intervals, real intervals, even partition positions in a hypothetical merged array.

The two parts of every binary search. The loop is the same in every implementation that ever shipped. The predicate is where the engineering judgment lives.

4. What the Constraints Tell Us

The textbook problem typically comes with constraints like n ≤ 10⁵ and use O(log n) time, O(1) extra memory. Each of these is doing work.

The size constraint, n ≤ 10⁵, is permissive — it allows anything from O(n) to O(n log n). It does not, by itself, force binary search.

The O(log n) constraint is the one that does. It rules out linear scan. It demands an algorithm that halves the search space at each step. And once we accept that we must halve, we are immediately committed to having a monotonic predicate — without one, we can't tell which half to halve.

A subtler implication of the O(log n) budget: evaluating the predicate must be cheap. The total cost of binary search is O(T_P · log |D|), where T_P is the cost of one predicate evaluation and |D| is the size of the domain. For the textbook problem, T_P = O(1) (a single array lookup and comparison), so the total cost is O(log n). For the binary-search-on-the-answer problems we'll meet in Section 9, the predicate is itself a simulation — and its cost matters. In Capacity to Ship, evaluating the predicate at a candidate capacity costs O(n), making the total cost O(n log W) where W is the answer space's width. Still much better than the brute alternatives.

The constraint we are not given explicitly — but which does all the structural work — is monotonicity. Without it, halving has no meaning. Half of an arbitrary predicate is just half of an arbitrary predicate. Monotonicity is what lets us extract information from a single midpoint evaluation.

The cost model. When the predicate is O(1), binary search is "the log algorithm." When the predicate is a simulation, the cost multiplies — and you trade O(n) per evaluation for log(answer space) evaluations.

5. The Transformation

Now we make the central move of the article.
Take the textbook problem and rewrite it in formal terms:

Given a sorted array A and target x, find the smallest index i such that A[i] ≥ x.

This is the standard lower_bound formulation. Notice what is interesting about it: we are not really searching for x. We are finding the boundary in the sequence of truth values of the predicate P(i) = (A[i] ≥ x).

i:        0   1   2   3   4   5   6   7
A[i]:     1   4   7   11  13  18  22  30
P(i):     F   F   F   F   T   T   T   T
                          ↑
                       boundary

The boundary index is the answer. Once you see this, you can ask the question that breaks the whole thing open:

Does binary search require an array?

No. It requires a predicate P over an ordered domain. The predicate must be monotonic: once it becomes true, it stays true. The domain must be ordered: we need to take midpoints. Binary search finds the boundary — the smallest element of the domain at which P is true — in O(log(|domain|)) evaluations of P. That is its actual signature.

The sorted-array problem is one instance. The domain happens to be the integer interval [0, n). The predicate happens to be A[i] ≥ x. The boundary happens to be the answer to "find x." But none of these are essential. Strip them away and you can apply the same algorithm to a dozen problems that don't look like search problems at all.

Consider:

Capacity to Ship Packages in D Days. You have an array of package weights. You have to ship them all in D days using a ship with capacity k. Each day, you load the ship with the next contiguous prefix of packages whose total weight is at most k, and you ship it. The question: what is the smallest capacity k such that all packages can be shipped within D days?

This sounds like a logistics problem, not a search problem. But look at the structure. Define P(k) = "we can ship in ≤ D days at capacity k". The predicate is monotonic: if you can do it at capacity k, you can certainly do it at any larger capacity (the larger ship is never worse). The answer is the smallest k for which P is true. The domain is the integer interval [max(weights), sum(weights)] — at minimum you need a ship that holds the largest single package; at maximum you need a ship that holds everything at once. Binary search the answer.

Koko Eating Bananas. Koko has n piles of bananas, with piles[i] bananas in pile i. She eats at some integer speed s bananas per hour. Each hour she picks a pile and eats up to s bananas from it (if the pile has fewer than s left, she finishes the pile and stops for the hour). The question: what is the smallest s such that she finishes all bananas within H hours?

Same shape, different surface. The predicate is P(s) = "she finishes in ≤ H hours at speed s". Monotonic in s. Domain [1, max(piles)]. Binary search the answer. The "eating bananas" surface is irrelevant; structurally this is identical to Capacity to Ship.

Square root of n. Given a positive number n, find the largest integer x such that x² ≤ n. Define P(x) = (x² > n). Monotonic in x. Domain [0, n]. Binary search the answer. If we want more precision than integer values give, the domain becomes the real interval [0, n], the predicate stays the same, and the halving loop terminates on a numerical tolerance instead of on integer convergence. The technique works on continuous domains as readily as discrete ones.

Median of Two Sorted Arrays. You have two sorted arrays A and B, of sizes m and n. Find the median of their union in O(log(min(m, n))) time. The naive solution merges them in O(m + n) and reads the middle. The O(log) solution is genuinely different: it does not search for the median value. It searches for the median partition position. We binary search on i ∈ [0, m], where i is the number of elements from A that go to the "left half" of the merged result. Given i, the corresponding partition j of B is determined arithmetically. The predicate is "is the partition valid?" — and we'll see in Section 9c that this predicate is monotonic in i. Binary search the partition position.

The transformation is not subtle. It is a single observation: if you have a monotonic predicate over an ordered domain, you have a binary-search problem. Most of the work in any non-trivial application is figuring out what the predicate should be. The halving loop is mechanical.

The article's centerpiece. Four problems with completely different surfaces (logistics, bananas, mathematics, partition positions) flatten to the same shape: a monotonic predicate over an ordered domain, with a single F → T boundary that is the answer. The substrate varies wildly; the algorithm is identical.

6. The Pattern, Named

The technique we just derived has a name: binary search on a monotonic predicate, sometimes called parametric search or binary search on the answer. It is older than computer science — versions of it appear in mathematics as the method of bisection for finding roots of continuous functions, going back at least to the work of Cauchy in the 1820s. The variant most readers learned — find x in a sorted array — is the special case where the predicate is A[i] ≥ x over the array's index range. Every other variant is the same idea over a different domain.

The general signature:

Inputs:
  - An ordered domain D, an interval [lo, hi]
  - A monotonic predicate P : D → {false, true}
Output:
  - The boundary: the smallest x ∈ D such that P(x) is true.

The pattern's signature in problem statements:

"Find the smallest/largest k such that…" — almost always.
"Minimize the maximum…" or "Maximize the minimum…" — the answer is monotonic in the bound; binary search on the bound.
"What is the smallest capacity/speed/value for which the simulation succeeds?" — binary search on the parameter.
"Find a value x such that f(x) = 0 and f is monotonic" — root-finding; same algorithm.

The pattern is older and more general than any single problem that uses it. Section 9 walks through three more variants in depth. Section 11 lists practice problems grouped by which flavor of monotonicity they exercise.

A reference card for the pattern. The visual signature is the F → T strip with two converging pointers; the trigger phrases are the words in a problem statement that should reach you for this technique..

7. Why It Works — A Proof

The algorithm is small enough that a full proof fits on one page. Here it is.

Setup. Let D = [lo, hi] be an integer interval. Let P : D → {false, true} be a predicate satisfying:

Monotonicity. If P(a) = true and b ≥ a, then P(b) = true.

Assume the boundary exists: there is some b ∈ D with P(b) = true. (If not, the algorithm will report no solution.)

Invariant. After each iteration of the binary search loop, the two pointers lo and hi satisfy:

P(lo - 1) = false, OR lo is the original starting value.
P(hi) = true, OR hi is one past the original ending value.

That is, the boundary lies in the half-open interval [lo, hi].

Loop body. At each iteration:

mid = lo + (hi - lo) / 2     // overflow-safe midpoint
if P(mid):
    hi = mid                  // boundary is at mid or to the left
else:
    lo = mid + 1              // boundary is strictly to the right

n each case the invariant is preserved, and the gap (hi - lo) decreases by at least half (rounded down).

Termination. Since the gap halves each iteration, after at most ⌈log₂(hi - lo)⌉ + 1 iterations the gap reaches zero. At that point lo == hi, and by the invariant this common value is the boundary.

Complexity. O(log |D|) evaluations of P. If P costs T_P per evaluation, the total cost is O(T_P · log |D|). For the textbook problem, T_P = O(1) and the total cost is O(log n). For binary-search-on-the-answer problems, T_P is the cost of the predicate simulation; total cost is O(T_P · log |answer space|).

Edge cases.

The boundary might be the first element of D (so P(lo) = true immediately). The invariant handles this — the loop terminates with lo == hi == original lo.
The boundary might not exist (P = false everywhere). The loop still terminates; we detect this case by checking P(lo) after the loop. If still false, return "no solution."
The real-valued case: replace integer halving with floating-point halving and terminate when hi - lo < ε. Termination is guaranteed within log₂((hi - lo) / ε) iterations.

Correctness in three claims. Half a page. The proof is short enough to keep in your head, which is the point.

8. Implementation in Go

The code is the proof, translated. Here is a generic binary-search-on-monotonic-predicate, written once and reused:

// Package bsearch provides binary search over any monotonic predicate.
package bsearch

// FindBoundary returns the smallest x in [lo, hi] for which p(x) is true.
// Returns hi + 1 if no such x exists in the interval.
//
// Precondition: p must be monotonic on [lo, hi] — once p(x) becomes true
// at some x, it stays true for all larger x in the interval.
//
// Runs in O(log(hi - lo)) evaluations of p.
func FindBoundary(lo, hi int, p func(int) bool) int {
    for lo < hi {
        mid := lo + (hi-lo)/2  // overflow-safe midpoint
        if p(mid) {
            hi = mid           // boundary at mid or left
        } else {
            lo = mid + 1       // boundary strictly to the right
        }
    }
    return lo
}

Twelve lines. Generic. Reusable. Now the textbook problem becomes a one-liner:

// Search finds the index of x in a sorted array, or -1 if absent.
func Search(arr []int, x int) int {
    i := FindBoundary(0, len(arr), func(i int) bool {
        return i < len(arr) && arr[i] >= x
    })
    if i < len(arr) && arr[i] == x {
        return i
    }
    return -1
}

And Capacity to Ship Packages, the non-obvious problem, becomes:

// ShipWithinDays returns the smallest capacity needed to ship all weights in <= D days.
func ShipWithinDays(weights []int, D int) int {
    maxW, sumW := 0, 0
    for _, w := range weights {
        if w > maxW {
            maxW = w
        }
        sumW += w
    }
    // The answer is in [maxW, sumW]. Find the smallest capacity k that suffices.
    return FindBoundary(maxW, sumW, func(k int) bool {
        days, cur := 1, 0
        for _, w := range weights {
            if cur+w > k {
                days++
                cur = 0
            }
            cur += w
        }
        return days <= D
    })
}

Notice what is the same and what is different. The FindBoundary call has the identical structure in both. What changed is the predicate. In Search, the predicate is arr[i] >= x, a single O(1) comparison. In ShipWithinDays, the predicate is a simulation of the shipping process at a given capacity — O(n) per evaluation. The total cost: O(n log(sumW)). Logarithmic in the answer space, linear per predicate evaluation.

The code makes the article's refrain visible. The FindBoundary function is the loop — the typing. The closure passed to it is the predicate — the thinking. Two different problems, identical loop, completely different thinking.

Search (left) and ShipWithinDays (right). The amber-highlighted regions are the predicate bodies; everything else is identical structurally. The left predicate is one comparison; the right one is a shipping simulation. Same loop, different thinking.

9. Generalisations and Worked Examples

Three flavours of the pattern. Koko is structurally identical to Capacity to Ship. Sqrt operates on a continuous domain and terminates on a tolerance. Median binary-searches on partition positions rather than values. The substrate changes; the algorithm doesn't.

a · Koko Eating Bananas

Same shape as Capacity to Ship, different story. Given a list of banana piles piles and a deadline H hours, find the smallest eating speed s such that Koko finishes all piles in ≤ H hours. At speed s, pile p takes ⌈p/s⌉ hours.

Domain: [1, max(piles)]. Predicate: P(s) = "total hours at speed s ≤ H". Monotonic in s: faster speeds finish in less time.

func MinEatingSpeed(piles []int, H int) int {
    maxP := 0
    for _, p := range piles {
        if p > maxP {
            maxP = p
        }
    }
    return FindBoundary(1, maxP, func(s int) bool {
        hours := 0
        for _, p := range piles {
            hours += (p + s - 1) / s  // ceiling division
        }
        return hours <= H
    })
}

The only thing distinctive about this implementation is the ceiling-division trick (p + s - 1) / s, which computes ⌈p / s⌉ using only integer arithmetic. Everything else is FindBoundary with a different predicate.

When you've seen two binary-search-on-the-answer problems with the same shape and completely different stories — packages and bananas — the shape starts to feel like the actual thing being studied. The logistics flavor of the first problem and the whimsical flavour of the second are surface decoration. The thinking is identical.

b · Square Root in Floating Point

Compute √n to six decimal places of precision, with no library functions.

This is the binary search problem with the most distinctively different substrate: the domain is a continuous interval rather than an integer one. The algorithm is structurally unchanged.

Domain: the real interval 0, n. Predicate: P(x) = (x² > n). Monotonic in x. The boundary is the value where x² = n — i.e., √n.

The only adjustment for floating point: the loop terminates not when lo == hi (which may never happen for reals) but when hi - lo < ε for some tolerance ε.

// Sqrt returns sqrt(n) to within epsilon = 1e-7.
func Sqrt(n float64) float64 {
    lo, hi := 0.0, n
    if n < 1.0 {
        hi = 1.0
    }
    for hi-lo > 1e-7 {
        mid := lo + (hi-lo)/2
        if mid*mid > n {
            hi = mid
        } else {
            lo = mid
        }
    }
    return lo
}

Same algorithm. Continuous domain. The technique doesn't care whether the underlying type is int or float64. What matters is the existence of a monotonic predicate and an ordered domain. Both hold here.

The convergence is geometric in the same sense as the integer case: each iteration halves the gap. For a starting gap of n ≈ 10 and a tolerance of 10⁻⁷, we need about log₂(10 / 10⁻⁷) ≈ 27 iterations. The square root of any reasonable double-precision number converges in fewer than 50 iterations of FindBoundary, which is faster than nearly any analytical alternative.

c · Median of Two Sorted Arrays

The deep cut. Given two sorted arrays A and B (sizes m and n), find the median of their union in O(log(min(m, n))) time.

The naive approach: merge A and B in O(m + n) and read the middle. Linear time. The O(log) approach is genuinely different — and the trick is that we are not searching for the median value. We are searching for the median partition position.

Without loss of generality assume m ≤ n (swap if necessary). Define i ∈ [0, m] as a partition of A: elements A[0..i) go to the "left half" of the merged array, A[i..m) to the right half. Given i, the corresponding partition j = ⌊(m + n + 1) / 2⌋ - i is the partition of B. The merged left half consists of A[0..i) ∪ B[0..j).

For i to be the correct partition, two conditions must hold:

B[j - 1] ≤ A[i]      (left of B doesn't overflow into right of A)
A[i - 1] ≤ B[j]      (left of A doesn't overflow into right of B)

(Edge values when i = 0, i = m, j = 0, or j = n are handled by treating the missing values as ±∞.)
The crucial fact: as i increases, A[i] increases and B[j - 1] decreases (because j decreases). So the first condition — B[j - 1] ≤ A[i] — is monotonic in i: at small i it is false (B has too many elements crammed into the left half), at large i it is true. This is the False → True shape FindBoundary expects. Binary search on i ∈ [0, m] for the smallest i where B[j - 1] ≤ A[i]; the second condition is automatically satisfied at that point (because of the symmetric monotonicity of A[i - 1] and B[j]).

import "math"

// FindMedianSortedArrays returns the median of A ∪ B.
func FindMedianSortedArrays(A, B []int) float64 {
    if len(A) > len(B) {
        A, B = B, A // ensure A is the shorter
    }
    m, n := len(A), len(B)
    half := (m + n + 1) / 2

    // Binary search on i: the smallest number of A-elements in the left half
    // such that B[j-1] ≤ A[i]. (Upper bound m+1 so i=m always satisfies.)
    i := FindBoundary(0, m+1, func(i int) bool {
        j := half - i
        aRight := math.MaxInt
        if i < m {
            aRight = A[i]
        }
        bLeft := math.MinInt
        if j > 0 {
            bLeft = B[j-1]
        }
        return bLeft <= aRight
    })

    j := half - i
    var leftMax int
    switch {
    case i == 0:
        leftMax = B[j-1]
    case j == 0:
        leftMax = A[i-1]
    default:
        leftMax = max(A[i-1], B[j-1])
    }

    if (m+n)%2 == 1 {
        return float64(leftMax)
    }

    var rightMin int
    switch {
    case i == m:
        rightMin = B[j]
    case j == n:
        rightMin = A[i]
    default:
        rightMin = min(A[i], B[j])
    }
    return float64(leftMax+rightMin) / 2.0
}

The implementation is longer because of the careful index arithmetic, but the structural move is the same as everything else in the article: FindBoundary over a monotonic predicate. The substrate is no longer "an array of values" — it is the partition position, an integer in [0, m]. Once we found the right i, the median is computed from the four boundary values in constant time.

This is the article's most dramatic example of substrate change. We are still binary-searching, but the domain is not a value space — it is a position space. The pattern doesn't care.

10. Where It Shows Up in Real Systems

The interesting question isn't can you solve LeetCode 704. It is: where does binary search appear in software that ships?

Database indexes. B-tree and B+tree lookups perform binary search at every level of the tree. The predicate is key ≤ target. Every relational database on Earth does this billions of times per day. Without it, an indexed query would be O(n) on the table size instead of O(log n) — the difference between a database and a flat file.

Compilers — scheduling and register allocation. Some scheduling heuristics binary-search the answer space for "smallest schedule length that satisfies all dependency constraints" or "smallest spill cost that allows the live ranges to fit in the available registers." The predicate is a feasibility check on the rest of the compiler's machinery; the search is on the bound.

Auction systems. Many auction designs (especially second-price and Dutch auction variants) compute the clearing price by binary-searching the price domain: "at price p, does total demand meet supply?" Monotonic in p. Production ad-auction systems lean on parametric search for clearing price computations.

Rate limiters and capacity planning. "What is the largest request rate at which 99% of requests succeed?" Binary search the rate. The predicate is a load test. This is parametric search at production scale, run continuously on infrastructure dashboards.

Scientific computing. Root-finding via bisection is exactly binary search on a continuous monotonic function. Used in everything from solving Kepler's equation for orbital mechanics to inverting cumulative distribution functions in statistical computing.

Storage engines. Log-Structured Merge Trees (used in Cassandra, LevelDB, RocksDB) maintain sorted runs of data; lookups within a run are binary search. The fact that the runs are merged in the background doesn't change the per-read algorithm.

Operating systems and networking. Page tables, route tables, and address-space mappings often use binary-searchable structures. Looking up a virtual address in a sparse page table is, structurally, a binary search.

In every case the surface looks different — a database B-tree, a compiler scheduler, an auction clearing price, a numerical solver. The underlying move is identical: a monotonic predicate over an ordered domain, halved until the boundary is found.

11. Problems That Exercise This Pattern

If you want to internalize the technique, here are problems where binary search on a monotonic predicate is the right tool. They are grouped by which flavor of monotonicity they exercise, not by difficulty.

Search on a sorted array (the boring case)

Binary Search — the canonical problem. Boundary on A[i] ≥ x.
First and Last Position in a Sorted Array — two boundaries instead of one. Call FindBoundary twice.
Search in Rotated Sorted Array — the array is sorted modulo a rotation. The predicate is subtler: "is mid in the same sorted half as lo?"
Find Peak Element — predicate: A[i] > A[i + 1]. The peak is on the side where this becomes true.

Binary search on the answer

Capacity to Ship Packages in D Days — the canonical "search the parameter; predicate is a simulation."
Koko Eating Bananas — same shape, different story.
Split Array Largest Sum — minimize the maximum chunk size.
Magnetic Force Between Two Balls — maximize the minimum gap.
Painter's Partition — minimize the maximum painter's workload.

Continuous / floating-point binary search

Square Root (no library) — the canonical continuous case.
Pow(x, n) with fractional precision — once formulated as a root-finding problem.
Find Right Interval — search position in sorted starts.

Cross-domain (the technique outside its native habitat)

Median of Two Sorted Arrays — binary search on partition position.
Aggressive Cows — game-theoretic flavor; same shape as Magnetic Force.
Kth Smallest Element in a Sorted Matrix — binary search on value, with a 2D predicate that counts elements ≤ candidate.

A practice exercise

For each problem above, before writing any code, name aloud:

What is the domain? — the variable you'll halve over.
What is the predicate? — the question whose answer is monotonic.
In which direction is it monotonic? — boundary on the left or the right?
What does evaluating the predicate cost?
Can the predicate be checked correctly at the boundary itself?

If you can answer these five questions in under a minute for any problem in the list, the pattern is yours.

What You Should Take Away

If you remember nothing else, remember the method.

We observed that the only structural fact binary search needs is that some predicate is monotonic over an ordered domain — not that we have a sorted array of values, though one happens to be sufficient. We decomposed binary search into two parts: the predicate (where the thinking lives) and the halving loop (which is mechanical). We read the constraint of O(log n) as a demand that we halve, which required monotonicity. We transformed "find x in a sorted array" into "find the boundary where the predicate A[i] ≥ x first becomes true" — and discovered that the predicate doesn't need to come from an array at all. The pattern that emerged — binary search on a monotonic predicate — appears across logistics, mathematics, compilers, databases, and scientific computing. And we proved correctness in three short claims: invariant, halving, termination.

That sequence — observe, decompose, read constraints, transform, recognize the pattern, prove it — is the template this series is built on. The problems change. The method does not.

Most courses teach binary search as a one-trick algorithm for sorted arrays. The arrays come first, the algorithm comes second, and the student leaves believing that binary search is for the rare moment when a sorted array drops into their lap.

But the technique is the other way around. The algorithm is general. The sorted-array case is a footnote. The interesting cases are everything else — the simulations whose feasibility is monotonic in some parameter, the continuous functions whose zeros we want to locate, the partition positions whose validity is monotonic in their offset.

The predicate is the thinking. The loop is the typing. The search came last. The search was never the point.

What make Rust blazing fast?

Sadanand Dodawadakar — Sat, 18 Jan 2025 10:48:30 +0000

Rust has earned immense popularity for being a blazing fast programming language, often competing or even outperforming established programming languages like C and C++. But what truly sets Rust apart? This story explores the technical features and design principles that make Rust a powerhouse for performance.

1. Zero-Cost Abstractions

Rust adheres to the principle of zero-cost abstractions, meaning that high-level constructs in the language introduce no additional runtime overhead. Features like iterators, closures, and traits compile down to highly optimised machine code.

let v = vec![1, 2, 3, 4];
let sum: i32 = v.iter().filter(|&&x| x % 2 == 0).sum();

Rust compiler optimises the iterator and filter into a loop with no abstraction penalty.

2. Memory Safety Without Garbage Collection

Unlike Java or Go, Rust achieves memory safety without relying on a garbage collector. This eliminates the performance overhead caused by periodic garbage collection pauses.

Ownership and Borrowing

Rust uses an ownership system with strict rules about how memory is accessed. The compiler ensures this at compile time.

Memory is not accessed after it is freed (no use-after-free errors).

Only one mutable reference or multiple immutable references exist simultaneously.

Deterministic Deallocation

Memory is deallocated immediately when it goes out of scope, akin to RAII in C++, leading to predictable performance.

3. Fearless Concurrency

Concurrency is notoriously difficult to get right due to data races. Rust enables “fearless concurrency” with its ownership model and type system.

Elimination of Data Races at Compile-Time
Data races are a common source of bugs and performance issues in concurrent systems. Rust leverages its ownership model and borrow checker to enforce concurrency rules at compile time

Exclusive Access: Rust ensures that data is either mutably borrowed by one thread or immutably borrowed by multiple threads, but not both. Two threads cannot mutate the same piece of data simultaneously.
No Undefined Behaviour: By catching concurrency issues during compilation, Rust eliminates runtime errors like segmentation faults, which can slow down or crash programs in other languages.

Compile-time safety ensures that Rust’s concurrent programs are “error-free by design”, eliminating expensive runtime checks, which often degrade performance.

Efficient Use of System Resources

Rust’s fearless concurrency directly translates to better system resource utilisation.

Fine-Grained Locking: Rust’s Mutex and RwLock primitives allow precise control over shared data, reducing contention and enabling efficient multi-threaded execution.

-** Zero-Cost Abstractions:** Unlike languages with garbage collection or runtime checks for thread safety, Rust relies on compile-time guarantees. This ensures no runtime performance penalties.
_

Low-Overhead Concurrency Primitives

Rust’s standard library provides efficient concurrency tools:

std::thread : Lightweight abstractions for spawning OS threads.
std::sync :High-performance synchronisation primitives like High-_performance synchronisation primitives like Condvar, Mutex , and RwLock.

Asynchronous Concurrency: Maximising Throughput

Rust’s asynchronous programming model, built around async/await, complements its multithreading capabilities:

Futures-Based Execution: Rust’s async tasks are lightweight and avoid blocking threads, allowing applications to handle millions of operations efficiently.
Event-Driven Execution: Frameworks like tokio and async-std use event loops to schedule tasks efficiently, reducing the need for expensive thread context switches._

Deterministic Behaviour and Predictable Performance

concurrency in Rust eliminates common pitfalls like race conditions and deadlocks:

Race Conditions: Rust enforces data access rules that prevent inconsistent states caused by unsynchronised threads.
Deadlocks: While Rust doesn’t eliminate deadlocks, its ownership model and explicit synchronisation primitives make potential deadlocks easier to identify and debug._

By eliminating these issues, Rust ensures that concurrent programs run “predictably and efficiently”, even under high workloads.

4. Monomorphisation of Generics

Rust uses monomorphisation for generics, generating specific code for each type used with a generic function or structure. This results in type-specific, highly optimised code at the cost of slightly larger binary sizes.

fn add<T: std::ops::Add<Output = T>>(a: T, b: T) -> T {
    a + b
}

fn main() {
    let int_sum = add(1, 2);      // Optimized for integers
    let float_sum = add(1.0, 2.0); // Optimized for floats
}

Compiler creates separate versions of add for integers and floats, eliminating runtime type checking and improving performance.

5. Minimal Runtime

One of the standout features of Rust is its minimal runtime overhead. This design choice ensures that Rust programs are not only safe and concurrent but also incredibly fast. Let’s break this concept down in detail.

Runtime overhead refers to the extra processing and resource consumption added by a language’s runtime environment to manage features like memory allocation, garbage collection, thread management, and more.

Languages like Java introduce significant runtime overhead due to their reliance on garbage collection and virtual machines (e.g., JVM for Java). Rust, on the other hand, avoids these overheads, delivering near-zero-cost abstractions and runtime efficiency.

6. Static Linking

Rust uses static linking by default, embedding all dependencies and required code directly into the executable. This ensures:

Faster runtime because there’s no need to dynamically resolve external libraries.
Predictable performance, as the binary includes everything needed for execution._

While this increases the executable size, it eliminates runtime delays due to dynamic linking, making execution faster. However, “static linking may increase the load time.”

We will do the comparison of rust compiled binary and C compiled binary to understand intricacies in details in the following sections.

7. LLVM Optimisations

Rust leverages the LLVM backend, which performs aggressive optimisations to generate highly efficient executables. Key LLVM optimisations include:

Inlining: Embeds function calls directly into the caller’s code to avoid the overhead of function calls.
Loop Unrolling: Optimises loops by reducing branching operations.
Dead Code Elimination: Strips unused code from the final executable, ensuring only essential instructions remain.

8. Low-Level Control with High-Level Guarantees

Rust allows direct control over hardware and memory, similar to C/C++, while maintaining safety through its ownership model. In cases where performance-critical operations are needed, unsafe blocks provide the freedom to bypass some safety checks for raw hardware access.

Rust ensures safe memory access by default, reducing debugging overhead.
Unsafe code regions, when necessary, compile to raw, low-level instructions without safety checks, maximising speed.

9. Efficient Memory Layout

Rust compilers carefully optimise data structures for cache alignment and memory layout. Using attributes like #[repr(C)], Rust ensures predictable layouts that match system architecture, reducing cache misses and improving access times.

#[repr(C)]
struct Point {
    x: f64,
    y: f64,
}

This ensures Point is laid out in memory as contiguous x and y values, enabling efficient hardware-level access.

10. LTO (Link-Time Optimisation)

Rust supports Link-Time Optimization (LTO), which optimizes the binary by analysing and optimising across crate boundaries. LTO ensures:

Removal of redundant code and function calls.
Cross-module inlining, improving execution speed._

[profile.release]
lto = "thin"

11. Whole-Program Compilation

Rust compiles the entire program, including dependencies, into a single executable. This enables the compiler to:

Inline functions across library boundaries.
Optimise the entire program holistically, unlike languages that compile individual files separately.

12. Optimised Panic Handling

Rust includes panic handling for safety, but it optimises for the common case where no panics occur:

Panic code paths are generated separately, leaving the main execution path lightweight.
Release builds can further strip panic messages for minimal overhead._

Final Thoughts

Rust’s speed is a product of deliberate design, combining low-level control, memory safety, and zero-cost abstractions to deliver exceptional performance. It excels in scenarios requiring both high efficiency and reliability, making it a compelling choice for modern systems.

Ultimately, Rust strikes a remarkable balance, offering developers the tools to build fast and safe software while acknowledging the complexity that comes with such power.

Generics in Go: Transforming Code Reusability

Sadanand Dodawadakar — Tue, 07 Jan 2025 16:25:47 +0000

Generics, introduced in Go 1.18, have revolutionised the way of writing reusable and type-safe code. Generics bring flexibility and power while maintaining Go’s philosophy of simplicity. However, understanding nuances, benefits, and how generics compare to traditional approaches (like interface{} ) requires a closer look.

Let’s explore the intricacies of generics, delve into constraints, compare generics to interface{}, and demonstrate their practical applications. We’ll also touch upon performance considerations and binary size implications. Let’s dive in!

What is Generics?

Generics allow developers to write functions and data structures that can operate on any type while maintaining type safety. Instead of relying on interface{}, which involves type assertions in runtime, generics let you specify a set of constraints that dictate the permissible operations on the types.

Syntax

func FunctionName[T TypeConstraint](parameterName T) ReturnType {
    // Function body using T
}

T: A type parameter, representing a placeholder for the type.

TypeConstraint: Restricts the type of T to a specific type or a set of types.

parameterName T: The parameter uses the generic type T.

ReturnType: The function can also return a value of type T.

Example

func Sum[T int | float64](a, b T) T {
    return a + b
}

func Sum: Declares the name of the function, Sum

[T int | float64]: Specifies a type parameter list that introduces T as a type parameter, constrained to specific types (int or float64). Sum function can take only parameters either int or float64, not in combination, both have to either int or float64. We will explore this further in below sections.

(a, b T): Declares two parameters, a and b, both of type T (the generic type).

T: Specifies the return type of the function, which matches the type parameter T.

Constraints: Building blocks of Generics

Constraints define what operations are valid for a generic type. Go provides powerful tools for constraints, including the experimental constraints package(golang.org/x/exp/constraints).

Built-in Constraints

Go introduced built-in constraints with generics to provide type safety while allowing flexibility in defining reusable and generic code. These constraints enable developers to enforce rules on the types used in generic functions or types.

Go has below built-in constraints

any: Represents any type. It’s an alias for interface{}. This is used when no constraints are needed

func PrintValues[T any](values []T) {
    for _, v := range values {
        fmt.Println(v)
    }
}

comparable: Allows types that support equality comparison(== and !=). Useful for maps keys, duplicate detection or equality checks. This can not be used for maps, slices and functions, since these types don’t support direct comparison.

func CheckDuplicates[T comparable](items []T) []T {
    seen := make(map[T]bool)
    duplicates := []T{}
    for _, item := range items {
        if seen[item] {
            duplicates = append(duplicates, item)
        } else {
            seen[item] = true
        }
    }
    return duplicates
}

Experimental constraints

constraints.Complex: Permits complex numeric types(complex64 and complex128).
constraints.Float: Permits float numeric types(float32 and float64)
constraints.Integer: Permits any integer both signed and unsigned (int8, int16, int32, int64, int, uint8, uint16, uint32, uint64 and uint)
constraints.Signed: Permits any signed integer(int8, int16, int32, int64 and int)
constraints.Unsigned: Permits any unsigned integer (uint8, uint16, uint32, uint64 and uint).
constraint.Ordered: Permits types that allow comparison (<. <=, >, >=), all numeric types and string are supported(int, float64, string, etc).

import (
     "golang.org/x/exp/constraints"
     "fmt"
)

func SortSlice[T constraints.Ordered](items []T) []T {
    sorted := append([]T{}, items...) // Copy slice
    sort.Slice(sorted, func(i, j int) bool {
        return sorted[i] < sorted[j]
    })
    return sorted
}

func main() {
    nums := []int{5, 2, 9, 1}
    fmt.Println(SortSlice(nums)) // Output: [1 2 5 9]

    words := []string{"banana", "apple", "cherry"}
    fmt.Println(SortSlice(words)) // Output: [apple banana cherry]
}

Custom Constraints

Custom constraints are interfaces that define a set of types or type behaviours that a generic type parameter must satisfy. By creating your own constraints, we can;

Restrict types to a specific subset, such as numeric types.
Require types to implement specific methods or behaviors.
Add more control and specificity to your generic functions and types.

Syntax

type Numeric interface {
    int | float64 | uint
}

Example

type Number interface {
    int | int64 | float64
}

func Sum[T Number](a, b T) T {
    return a + b
}

Sum function can be called using only int, int64 and float64 parameters.

Constraints by method

If you want to enforce a type must implement certain methods, you can define it using those methods.

type Formatter interface {
    Format() string
}

func PrintFormatted[T Formatter](value T) {
    fmt.Println(value.Format())
}

The Formatter constraint requires that any type used as T must have a Format method that returns a string.

Combining Constraints

Custom constraints can combine type sets and method requirements

type AdvancedNumeric interface {
    int | float64
    Abs() float64
}

func Process[T AdvancedNumeric](val T) float64 {
    return val.Abs()
}

This constraint includes both specific types (int, float54) and requires the presence of an abs method.

Generics vs interface{}

Before introduction of generics, interface{} was used to achieve flexibility. However, this approach has limitations.

Type Safety

interface{}: Relies on runtime type assertions, increasing the chance of errors at runtime.
Generics: Offers compile-time type safety, catching errors early during development.

Performance

interface{}: Slower due to additional runtime type checks.
Generics: Faster, as the compiler generates optimised code paths specific to types.

Code Readability

interface{}: Often verbose and less intuitive, making the code harder to maintain.
Generics: Cleaner syntax leads to more intuitive and maintainable code.

Binary Size

interface{}: Results in smaller binaries as it doesn’t duplicate code for different types.
Generics: Slightly increases binary size due to type specialisation for better performance.

Example

func Add(a, b interface{}) interface{} {
    return a.(int) + b.(int)
}

Code works well, type assertion is overhead. Add function can called with any argument, both a and b parameters can be of different types, however code will crash in the runtime.

func AddGeneric[T int | float64](a, b T) T {
    return a + b
}

Generics eliminate the risk of runtime panics caused by incorrect type assertions and improve clarity.

Performance

Generics produce specialised code for each type, leading to better runtime performance compared to interface{}.

Binary Size

A trade-off exists: generics increase binary size due to code duplication for each type, but this is often negligible compared to the benefits.

Limitations of Go Generics

Complexity in Constraints: While constraints like constraints.Ordered simplify common use cases, defining highly customized constraints can become verbose.

No Type Inference in Structs: Unlike functions, you must specify the type parameter explicitly for structs.

s := Stack[int]{} // Type parameter is required

Limited to Compile-Time Constraints: Go generics focus on compile-time safety, whereas languages like Rust offer more powerful constraints using lifetimes and traits.

Let’s Benchmark — Better done than said

We will implement a simple Queue with both interface{} and generic and benchmark the results.

Interface{} Queue implementation

package main

import (
 "testing"
)

type QueueI struct {
 items []interface{}
}

func (q *QueueI) Enqueue(item interface{}) {
 q.items = append(q.items, item)
}

func (q *QueueI) Dequeue() interface{} {
 item := q.items[0]
 q.items = q.items[1:]
 return item
}

func BenchmarkInterfaceQueue(b *testing.B) {
 queue := QueueI{}
 for i := 0; i < b.N; i++ {
  queue.Enqueue(i)
  queue.Dequeue()
 }
}

Generic Queue Implementation

package main

import (
 "testing"
)

type QueueG[T any] struct {
 items []T
}

func (q *QueueG[T]) Enqueue(item T) {
 q.items = append(q.items, item)
}

func (q *QueueG[T]) Dequeue() T {
 item := q.items[0]
 q.items = q.items[1:]
 return item
}

func BenchmarkGenericQueue(b *testing.B) {
 queue := QueueG[int]{}
 for i := 0; i < b.N; i++ {
  queue.Enqueue(i)
  queue.Dequeue()
 }
}

go test -bench=. -benchmem
goos: darwin
goarch: amd64
pkg: becnh
cpu: VirtualApple @ 2.50GHz
BenchmarkGenericQueue-10        74805141                16.05 ns/op            8 B/op          1 allocs/op
BenchmarkInterfaceQueue-10      25719405                44.65 ns/op           24 B/op          1 allocs/op
PASS
ok      becnh   4.522s

Analysis of Results

Execution Time:
The generic implementation is approximately 63.64% faster than the interface{} version because it avoids runtime type assertions and operates directly on the given type.
Allocations:
The interface{} version makes 3x more allocations, primarily due to boxing/unboxing when inserting and retrieving values. This adds overhead to garbage collection.

For larger workloads, such as 1 million enqueue/dequeue operations, the performance gap widens. Real-world applications with high-throughput requirements (e.g., message queues, job schedulers) benefit significantly from generics.

Final Thoughts

Generics in Go strike a balance between power and simplicity, offers a practical solution for writing reusable and type-safe code. While not as feature-rich as Rust or C++, align perfectly with Go’s minimalist philosophy. Understanding constraints like constraints.Ordered and leveraging generics effectively can greatly enhance code quality and maintainability.

As generics continue to evolve, they are destined to play a central role in Go’s ecosystem. So, dive in, experiment, and embrace the new era of type safety and flexibility in Go programming!

Checkout github repository for some samples on generics.

sadananddodawadakar / GoGenerics

Repository contains working examples of go generics

Go Generics: Comprehensive Examples Repository

Welcome to the Go Generics Repository! This repository is a one-stop resource for understanding, learning, and mastering generics in Go, introduced in version 1.18. Generics bring the power of type parameters to Go, enabling developers to write reusable and type-safe code without compromising on performance or readability.

This repository contains carefully curated examples that cover a wide range of topics, from basic syntax to advanced patterns and practical use cases. Whether you're a beginner or an experienced Go developer, this collection will help you leverage generics effectively in your projects.

🚀 What's Inside

🔰 Basic Generic Programs

These examples introduce the foundational concepts of generics, helping you grasp the syntax and core features:

GenericMap: Demonstrates a generic map function to transform slices of any type.
Swap: A simple yet powerful example of swapping two values generically.
FilterSlice: Shows how to filter…

View on GitHub

Hidden Power of Go: Unveiling the Secrets of a Robust Language

Sadanand Dodawadakar — Wed, 01 Jan 2025 20:49:20 +0000

Golang is celebrated for its simplicity, efficiency, and developer-friendly features. While most developers are familiar with Go’s hallmark features like go-routines, channels, and its standard library, there’s a wealth of hidden power. In this article, we will explore Go’s lesser-known capabilities that can significantly enhance your development process and application performance.

The runtime Package: A Peek Under the Hood

The runtime package offers a set of tools that allow you to inspect and manipulate Go’s runtime system. It’s not just for debugging; it’s also a window into how Go works.

Go-routine Inspection
The runtime.NumGoroutine function provides the current number of goroutines running in your application, useful for monitoring concurrency.

package main

import (
    "fmt"
    "runtime"
)

func main() {
    fmt.Printf("Number of Goroutines: %d\n", runtime.NumGoroutine())
}

*Callers and Callstack *
Using runtime.Callers and runtime.CallersFrames, you can inspect the call stack programmatically. This is especially useful in debugging complex issues.

package main

import (
    "fmt"
    "runtime"
)


func printCallers() {
    pc := make([]uintptr, 10)
    n := runtime.Callers(2, pc)
    frames := runtime.CallersFrames(pc[:n])
    for frame, more := frames.Next(); more; frame, more = frames.Next() {
        fmt.Printf("%s\n    %s:%d\n", frame.Function, frame.File, frame.Line)
    }
}

Manual Garbage Collection:
While Go has an automatic garbage collector, you can trigger garbage collection manually using runtime.GC() in scenarios where deterministic cleanup is necessary.

package main

import (
    "fmt"
    "runtime"
)

func InvokeGC() {
    runtime.GC()
}

Dynamic Memory Stats:
Use runtime.ReadMemStats to gather detailed memory usage statistics, aiding in performance optimisation.

package main() 

import (
    "fmt"
    "runtime"
)

func PrintMemStates() {
    var stats runtime.MemStats
    runtime.ReadMemStats(&stats)
    fmt.Printf("Allocated memory: %v KB\n", stats.Alloc/1024)
}

Advanced Debugging with the debug Package

The debug package complements runtime by offering tools for deep runtime diagnostics. It’s especially useful for debugging complex issues in production.

Stack Trace Retrieval
The debug.Stack function lets you capture stack traces programmatically for logging or monitoring purposes.

package main

import (
    "fmt"
    "runtime/debug"
)

func main() {
    fmt.Printf("Stack Trace:\n%s\n", debug.Stack())
}

Symbolic Metadata

Access build information, including dependencies and module versions, using debug.ReadBuildInfo. This is invaluable for debugging version mismatches in production.

package main

import (
    "fmt"
    "runtime/debug"
)

func main() {
    info, ok := debug.ReadBuildInfo()
    if ok {
        fmt.Printf("Build Info:\n%s\n", info.String())
    }
}

Memory Management
The debug.FreeOSMemory function forces the release of unused memory back to the operating system, which can be a lifesaver in resource-constrained environments.

package main

import (
    "fmt"
    "runtime/debug"
)

func triggerGCWithFreeOSMemeory() {
    debug.FreeOSMemory
}

Embedding Files with embed: Simplified Asset Management

Introduced in Go 1.16, the embed package allows you to include files and directories into your Go binaries, making it easier to distribute standalone applications.

package main

import (
    "embed"
    "fmt"
)

//go:embed config.json
var configFile string

func main() {
    fmt.Println("Embedded Config:", configFile)
}

This eliminates the need for external configuration file management during deployment.

Build Tags: Conditional Compilation

Go’s build tags allow you to include or exclude files during compilation based on conditions like OS or architecture.

// +build linux

package main

import "fmt"

func main() {
    fmt.Println("This code runs only on Linux.")
}