On this page

Other Searches: Ternary, Exponential, Interpolation, Meet-in-the-Middle

Binary search answers one question optimally: find the boundary of a monotone predicate over a known range, using only comparisons. Change any part of that question and a different search wins. If the function goes up then down instead of false-then-true, you need ternary or golden-section search. If you do not know where the range ends, exponential search finds it in for a target at position . If the keys are numbers spread roughly evenly, interpolation search guesses the position from the value and needs about probes — 4 instead of 20 for a million keys. If the search space is not an array at all but the subsets of 40 numbers, meet-in-the-middle splits it into two halves of and searches one against the other. This lesson covers each: when it applies, why it works, the exact conditions under which it fails, and what it costs.

Lesson position: Module 2 · Searching & Sorting · previous: Binary Search Mastery · next: Quickselect & Order Statistics · course map.

Why this exists

The comparison lower bound says that finding one of positions with yes/no comparisons takes probes in the worst case. Every technique here either changes the question so the bound does not apply, or changes the information per probe so it is beaten.

Ternary search changes the question. Finding the maximum of a unimodal function is not a boundary search over a predicate you can evaluate at one point — whether you are left or right of the peak cannot be decided from one value — so it compares two interior points. Jack Kiefer worked out the optimal strategy in 1953 ("Sequential minimax search for a maximum"): Fibonacci search for a fixed number of evaluations, and its limit, golden-section search, which reuses one evaluation per step and shrinks the interval by per new evaluation. These are the basic line-search tools of numerical optimisation.

Exponential search changes the setting: the array is unbounded, or the target is probably near the start. Bentley and Yao (1976, "An almost optimal algorithm for unbounded searching") analysed it; Tim Peters used it as "galloping" inside Timsort's merge (see Sorting in the Real World), where it lets merging two barely-overlapping runs cost instead of .

Interpolation search changes the information: a comparison tells you only "less or greater", but the key's value tells you roughly where it should be — the way you open a phone book near "S" for "Smith". On uniformly distributed keys, Perl, Itai and Avni proved in 1978 ("Interpolation search — a log log N search", Communications of the ACM 21(7)) that the expected number of probes is . On adversarial keys it degrades to .

Meet-in-the-middle changes the search space. Problems over items with candidate subsets are too big for brute force () but split cleanly into two independent halves whose partial results can be sorted or hashed and matched. The idea is old in cryptanalysis — Diffie and Hellman used it in 1977 to show why encrypting twice with DES gives far less than double the key strength — and it is a staple of competitive programming.

Pattern triggers

If the problem says or has…Think of…
"maximise / minimise " where increases then decreases (or is convex)Ternary search or golden-section search; on integers, binary search on the slope
"mountain array", "bitonic", "single peak"Binary search on a[m] < a[m+1] (cleaner than ternary on arrays)
A continuous convex cost (distance sums, time to meet, error of a fit)Golden-section / ternary on reals with a fixed iteration count
"array of unknown size", "infinite sorted stream", reader API with out-of-range sentinelExponential search: find the bound by doubling, then binary search
"the target is probably near the beginning", merging runs that barely overlapExponential (galloping) search,
Sorted numeric keys, roughly uniform (IDs, timestamps, hashes)Interpolation search — but guard against skew
Expensive backward movement (tape, singly-linked blocks), block-structured storageJump search with step , or a two-level index
items, subsets, "sum exactly / closest to ", values up to or moreMeet-in-the-middle: per half, sort + binary search or two pointers
"count quadruples with "Meet-in-the-middle with a hash map of pair sums,
Shortest path between two known nodes in a huge implicit graph (word ladders, puzzles)Bidirectional BFS — meet-in-the-middle on a graph
Values too large for a DP table ( up to ) and too large for Meet-in-the-middle is often the only option

Intuition & first principles

Unimodal functions need two probes. Suppose strictly increases on and strictly decreases on . Evaluate at one interior point : the value alone cannot tell you which side of the peak is on. Evaluate at two points : if , the peak cannot be left of — if it were, would be decreasing on and . So discard . Symmetrically, discards . Placing at the thirds discards a third each time. The clever refinement — golden section — places them so that the surviving interior point is exactly where the next step needs one of its two points, so each step costs one new evaluation instead of two.

Unknown bounds need doubling. If you cannot binary search because you do not know , find one: probe positions 1, 2, 4, 8, … until the value passes the target. If the target is at position , this takes probes and leaves a range of size at most for an ordinary binary search. Total — better than when , and the only option when is unknown.

Values carry more than order. Binary search always probes the middle. If the array holds 1,000,000 keys spread evenly between 0 and and you seek 9,800,000, the key is almost certainly near position 980,000 — probing the middle wastes most of what you know. Interpolation search probes where linear interpolation between the endpoints says the key should be. On uniform data the first probe lands within about positions of the target, the next within about , and so on: the exponent halves each time, which is why the count is .

Splitting the search space halves the exponent. Brute-force subset sum over items checks subsets. Any subset is a choice from the first half combined with a choice from the second half, and its sum is the sum of the two parts. So enumerate the sums of each half, sort one list, and for each sum in the other list look up . Time , memory . The square root of an exponential is still exponential, but is a million and is a trillion.

flowchart TD
    Q["What do you know about the search space?"] --> M{"Monotone predicate,<br/>known bounds?"}
    M -->|"yes"| BS["Binary search<br/>O(log n)"]
    M -->|"bounds unknown"| EX["Exponential search<br/>O(log i)"]
    Q --> U{"Unimodal or convex<br/>function?"}
    U -->|"reals"| GS["Golden-section / ternary<br/>fixed iterations"]
    U -->|"integers"| SL["Binary search on slope<br/>f(m) vs f(m+1)"]
    Q --> V{"Numeric keys,<br/>roughly uniform?"}
    V -->|"yes"| IS["Interpolation search<br/>O(log log n) expected"]
    Q --> S{"2^n subsets,<br/>n up to 40?"}
    S -->|"yes"| MM["Meet-in-the-middle<br/>2^n/2 sums per half"]

Mechanics

Ternary search on reals

Requirement: strict unimodality. must strictly increase up to the maximiser and strictly decrease after it (for minimisation, the mirror image; strictly convex functions qualify). Each iteration:

  1. , .
  2. If , set ; otherwise set .

The interval shrinks to of its width per iteration, at two evaluations per iteration.

Trace: minimise on (minimisation, so keep the side with the smaller value; computed by script, four decimals):

IterlohiDecisionNew interval
10.00007.00002.33331.11114.66678.1111: drop right[0.0000, 4.6667]
20.00004.66671.55561.19753.11112.2346drop right[0.0000, 3.1111]
30.00003.11111.03701.92732.07411.0055drop left[1.0370, 3.1111]
41.03703.11111.72841.07382.41981.1762drop right[1.0370, 2.4198]

The minimiser 2 stays inside the interval at every step; after 52 iterations (104 evaluations) the interval is of its original width.

Why strictness matters. If has a flat region that is not the optimum, a tie carries no information. Take on except a narrow spike peaking at . The first thirds are , , both with ; the tie falls to the "otherwise" branch, which sets and throws away the spike for good. Swapping the tie rule only moves the failure: a spike at is then discarded instead. Ternary search on a function with plateaus below the optimum is simply incorrect. Ties are safe only under strict unimodality, where equal values must straddle the peak and either discard is valid.

Ternary search throws away both evaluations every step. Golden-section search places the interior points at fractions and of the interval, where . After discarding one end, the surviving interior point sits exactly at the 0.382 or 0.618 position of the new interval — because — so only one new evaluation is needed per step. Each new evaluation shrinks the interval by a factor ; ternary search shrinks by per evaluation. To shrink an interval by :

MethodShrink per stepEvaluations for (computed)
Ternary search per 2 evaluations104
Golden-section search per 1 evaluation45
Binary search on (sign of derivative) per derivative evaluation30 derivative evaluations
Binary search on per 2 evaluations60

Comparison to binary search on the derivative. For a differentiable unimodal , the derivative is positive left of and negative right of it — a monotone predicate — so binary search on the sign of finds with one derivative evaluation per halving. If is available cheaply, that wins. Without a derivative, approximating it by costs two evaluations per halving (60 for ), still worse than golden section's 45, and must be chosen carefully against floating-point noise. On integers this approach is the clean one: comparing f(m) with f(m + 1) is exact, and "is still increasing at ?" is a monotone predicate for strictly unimodal — it is exactly Find Peak Element. That is why on integer domains you should usually prefer binary search on the slope over integer ternary search, whose termination conditions are fiddly.

Integer ternary trace on the strictly unimodal array [1, 3, 8, 12, 15, 14, 9, 4, 2], looping while the range has more than three elements:

lohiUpdate
082689: lo = 3
3847154hi = 6
36451514hi = 4
34————scan [3, 4]: max at index 4 (15)
if a[0] >= t: return 0 (or not found)
bound = 1
while bound < n and a[bound] < t: bound *= 2
binary search for t in [bound / 2, min(bound, n - 1)]

When the loop stops, a[bound/2] < t (it was probed and was too small, or bound/2 = 0 and was checked first) and either bound >= n or a[bound] >= t, so the target, if present, is in . Trace: find 37 in the 16 primes [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53]:

ProbeIndexValue?Next bound
113yes2
225yes4
3411yes8
4823yes16
—16out of rangestop—

Binary search in then finds 37 at index 11. If the target is at position , the doubling phase takes about probes and the binary phase searches a range of size , so the total is — at most twice binary search's cost on an array of size , and independent of .

Unbounded arrays. LeetCode 702 gives a sorted array behind an ArrayReader that returns a sentinel past the end; exponential search finds the bound without knowing . The same idea finds the size of an unknown file by doubling seeks, and the version-number range in which a regression appeared.

Use in Timsort. When merging runs and , Timsort first gallops to find where belongs in (everything before it is already in place) and, in galloping mode, how many consecutive elements of the winning run precede the other run's head. Galloping from the current position makes the cost logarithmic in the distance moved, not in the run length — Bentley–Yao's unbounded search is exactly the right tool. Galloping wastes comparisons on random data, which is why Timsort enters it only after one run wins 7 times in a row.

Probe the position that linear interpolation predicts:

and continue on the side that can contain , exactly like binary search, while . On evenly spaced data it is perfect: in [10, 20, …, 100], searching for 70 gives — found in one probe.

Measured probe counts (random sorted samples of distinct integers from , averaged over up to 2,000 successful searches; computed by script):

Interpolation, avg probesBinary, avg probes
1,0003.558.993.32
10,0003.6812.363.73
100,0003.8015.664.05
1,000,0004.1418.984.32

Going from a thousand to a million keys adds about 0.6 probes to interpolation search and 10 to binary search.

The worst case is . Take [1, 2, 3, …, n-1, 10^12] and search for . The huge last key makes every interpolation land at lo, so each probe advances by one position: measured 999, 9,999 and 99,999 probes for , , , where binary search needs 9, 13 and 16. Milder skew hurts too — on the powers of two [1, 2, 4, …, 1024], searching for 256 probes indices 2, 4, 6, 7, 8 (five probes for eleven elements, worse than binary search's four).

Proof sketch of (Perl, Itai, Avni 1978; also Yao and Yao 1976). Suppose the keys are independent uniform samples from . The number of keys below is then binomially distributed with mean (where is 's relative position) and standard deviation . The interpolated position is exactly that mean, so the probe misses the true position by about on average (Chebyshev bounds the probability of missing by much more). The keys in the remaining subrange are again uniform on their own value range, so the next probe misses by about , then , and so on. After probes the uncertainty is , which reaches a constant when , i.e. . The rigorous proof handles the fact that the "remaining subrange" is determined by the probe outcomes (conditioning), and gives expected probes . On non-uniform data the argument fails at the first step — the interpolated position is not the expected position — which is the case above.

Safer variants. Interpolation–sequential search probes once by interpolation and then scans; interpolation-binary hybrids alternate an interpolation probe with a binary probe (or fall back to bisection when an interpolation step shrinks the range by less than half), guaranteeing worst case while keeping on uniform data. In practice, a learned index (below) is the modern descendant.

Divide the sorted array into blocks of elements. Check the last element of each block, jumping forward, until one is ; then scan that block linearly. Cost: at most jumps plus scans, minimised at , giving at most about comparisons — 2,000 for , against 20 for binary search. For the even numbers [0, 2, …, 198] (, step 10) searching for 150 takes 14 comparisons: 8 block checks (the eighth, , stops the jumping), then 6 scan steps to index 75.

That looks strictly worse than binary search, and on a RAM array it is. Its virtue is that it only moves forward and touches memory in blocks: on media where going backward is expensive (tape, a singly-linked list of blocks, a compressed stream that can only be decoded forward) or where reading a block costs the same as reading one element, jump search's access pattern is the right one. The real-world form is the two-level index: keep the first key of every block in memory (the "jump" table), binary search it, then read one block — which is how SSTable indexes, Kafka's offset index and B-trees work. The choice reappears in Sparse Tables & Sqrt Decomposition.

Fibonacci search (briefly)

Fibonacci search splits the range at Fibonacci-number offsets instead of halves: with the range length a Fibonacci number , probe at offset , and the surviving piece has length or . It uses only addition and subtraction to compute probe positions (historically valuable when division was slow), and successive probes are closer together than in binary search, which helped on drums and tapes. Its worst case is about comparisons; on average it is only slightly worse than binary search (Knuth, Vol. 3, §6.2.1, analyses both). Searching for 85 in [10, 22, 35, 40, 45, 50, 80, 82, 85, 90, 100] probes indices 4, 7, 9, 8. On unimodal functions, Fibonacci search is Kiefer's optimal strategy for a fixed evaluation budget, and golden-section search is its limit as the budget grows.

Meet-in-the-middle

Subset sum with . Count (or find) subsets of 40 integers — values up to , so no DP table over sums — that sum to .

  1. Split the items into halves and of 20 each.
  2. Enumerate all subset sums of each half (doubling: start with [0], and for each item append every existing sum plus the item).
  3. Sort the sums of .
  4. For each sum of , count occurrences of in sorted with two binary searches (upper_bound - lower_bound), or sort both and sweep with two pointers.

Time — about basic steps for — versus for brute force. Memory : about 8 MB per half as 64-bit integers. A Python run of exactly this on 40 random values around – took about 1.4 seconds.

flowchart LR
    A["40 items"] --> L["Left 20 items"]
    A --> R["Right 20 items"]
    L --> LS["2^20 subset sums<br/>of left"]
    R --> RS["2^20 subset sums<br/>of right, sorted"]
    LS --> J["for each s in left:<br/>count T - s in right<br/>by binary search"]
    RS --> J
    J --> OUT["number of subsets<br/>with sum T"]

Trace on [3, 34, 4, 12, 5, 2], : , .

Left sums: 0, 3, 4, 7, 34, 37, 38, 41. Right sums (sorted): 0, 2, 5, 7, 12, 14, 17, 19.

Left sum Need Count in rightSubsets found
090—
360—
451{4} + {5}
721{3, 4} + {2}
34, 37, 38, 41negative0—

Total 2, matching brute force over all 64 subsets.

4-sum counting. Given four arrays of length , count tuples with . Brute force is ; meet-in-the-middle puts all sums in a hash map with counts, then for each of the sums adds count[-(c + d)]. time and space. For , , , : the map is , and the sums match with counts 1 and 1 — answer 2 (LeetCode 454's example). See Hash Tables.

Bidirectional search. Searching for a shortest path from to in a graph with branching factor and distance , BFS from explores about nodes. Running BFS from both ends and stopping when the frontiers meet explores about — the same square-root saving. With and that is versus nodes. It needs an explicit target and reversible edges, and it is covered as bidirectional BFS in the graph module (see the current Graphs page in the meantime).

Cryptanalysis. Encrypting twice with two independent 56-bit DES keys — — looks like a 112-bit cipher, but with one known plaintext/ciphertext pair an attacker encrypts under all keys, decrypts under all keys, and matches the middle values: about work and memory instead of . This is why "Triple DES" exists rather than "Double DES". The generic baby-step giant-step algorithm for discrete logarithms is the same split with a time–memory trade. See Cryptography for Engineers.

Sqrt-style search trade-offs

A recurring pattern across this page: split a size- search into two stages of size each, paying memory or preprocessing to cut time.

TechniqueSplitTimeExtra memoryTrade
Jump search blocks of noneforward-only, block access
Two-level index (SSTable, B-tree root)index of block heads + one block block read keys in RAMmemory for I/O
Meet-in-the-middle subset summemory for time
Schroeppel–Shamir (1981)four quarters, heap-mergedreduces MITM memory
Baby-step giant-step baby steps, giant stepsmemory for time
Bidirectional BFStwo half-depth searchesneeds known target

Meet-in-the-middle is a time–memory trade-off: memory is the price. For it is trivial; for it is entries, 8 GB, and Schroeppel–Shamir's -memory variant becomes the practical choice.

The ladder: brute force → better → optimal

Problem: count subsets of integers (values up to ) whose sum is exactly .

Rung 1 — enumerate all subsets. Recursion or bitmask over subsets, amortised per subset with Gray-code updates. At simple operations per second that is about 18 minutes in C++, days in Python. Correct; hopeless at contest or interactive scale.

Rung 2 — dynamic programming over sums. count[s] = number of subsets with sum , updated item by item: for total sum . Excellent when values are small (): 40 million steps. Useless here: reaches . This rung improves on brute force only when values are small — the key observation is that rung 2 and rung 3 attack different constraints.

Rung 3 — meet-in-the-middle with sort + binary search. Two halves of sums; sort one, binary search for each element of the other. , about operations, independent of the values' magnitude.

Rung 4 — meet-in-the-middle with sorted merge / two pointers. Generate each half's sums already sorted by merging (each new item merges the list with itself shifted by the item, per step), then sweep both sorted lists with two pointers. total — the factor disappears. A hash map of one half's counts also gives expected , with worse constants and memory.

RungTimeMemoryWorks when
1. All subsets or so
2. DP over sumstotal sum small
3. MITM + binary search–, any values
4. MITM + sorted generation + two pointerssame, about 2–3× faster

Correctness

Invariant: the maximiser lies in .

Maintenance. Let be in . If , suppose for contradiction that . Then and both lie on the strictly decreasing side, so — contradiction. Hence and still contains it. If , symmetrically . If , under strict unimodality the two points cannot be on the same side (that would force strict inequality), so and either discard is safe.

Progress. Each step shrinks the width to ; after steps it is , so the loop reaches any tolerance. For golden section the same argument applies with width factor per step.

The proof uses strictness exactly once — in the equal case — and that is precisely where non-strict unimodal functions break.

Bound phase. Invariant: every probed index satisfies . When the loop exits, either or . Since is sorted and (or and was checked), the first index with lies in . Binary phase. lower_bound on that range is correct by the first-true theorem. Cost. If the answer is at , the loop stops once , i.e. after probes, and the final range has fewer than elements.

Interpolation search

The interpolated satisfies whenever and (the fraction is in ). Each step either finds or removes and everything on one side of it, maintaining "if is present it is in ", exactly as in binary search. So it is always correct and terminates in at most probes; only its speed depends on the distribution. The case must be handled separately (division by zero): then all keys in the range are equal and one comparison decides.

Meet-in-the-middle

Each subset of the items corresponds to exactly one pair , and . The algorithm counts pairs from the multisets of left and right subset sums with ; the multisets contain one entry per subset (duplicates kept), so pairs correspond one-to-one with subsets summing to . Counting upper_bound - lower_bound of counts every matching including duplicates. For 4-sum, the same bijection holds between tuples and pairs (left pair, right pair).

Complexity

SearchProbes / timeSpacePreconditions
Ternary (reals) iterations, 2 evals eachstrictly unimodal
Golden-section evaluationsstrictly unimodal
Binary on slope (integers)strictly unimodal
Exponentialsorted; may be unknown
Interpolation expected (uniform); worstsorted numeric keys
Jump, at sorted
Fibonacci, about worstsorted
Meet-in-the-middle subset sum, or with mergingsplittable search space
4-sum counting expectedhashable sums

Constants. Interpolation search's probe count is small, but each probe does a multiplication and a division (and in fixed-width integers, a 128-bit or floating-point product to avoid overflow), and its probes are data-dependent jumps across memory — on arrays that fit in cache, a branchless binary search is often faster in wall-clock terms despite 5× more probes. It wins when probes are expensive (disk pages, network round trips). Meet-in-the-middle is memory-bandwidth bound: sorting 64-bit sums is fast, but (for ) is 256 MB per half, at which point cache misses dominate.

Implementation

The canonical implementation contains four functions with the same tests in all languages: exponential search (returns the index or −1), interpolation search (with the equal-endpoints guard and overflow-safe arithmetic), integer ternary search for the maximum of a strictly unimodal array, and meet-in-the-middle counting of subsets with a given sum, checked against counts computed by dynamic programming.

from bisect import bisect_left, bisect_right


def exponential_search(a: list[int], t: int) -> int:
    n = len(a)
    if n == 0:
        return -1
    if a[0] >= t:
        return 0 if a[0] == t else -1
    bound = 1
    while bound < n and a[bound] < t:
        bound *= 2
    lo, hi = bound // 2 + 1, min(bound, n - 1) + 1     # a[bound // 2] < t is known
    i = bisect_left(a, t, lo, hi)
    return i if i < n and a[i] == t else -1


def interpolation_search(a: list[int], t: int) -> int:
    lo, hi = 0, len(a) - 1
    while lo <= hi and a[lo] <= t <= a[hi]:
        if a[hi] == a[lo]:                            # all equal: avoid division by zero
            return lo if a[lo] == t else -1
        pos = lo + (t - a[lo]) * (hi - lo) // (a[hi] - a[lo])
        if a[pos] == t:
            return pos
        if a[pos] < t:
            lo = pos + 1
        else:
            hi = pos - 1
    return -1


def ternary_max_index(a: list[int]) -> int:
    """Index of the maximum of a strictly unimodal array (strictly up, then strictly down)."""
    lo, hi = 0, len(a) - 1
    while hi - lo > 2:
        m1 = lo + (hi - lo) // 3
        m2 = hi - (hi - lo) // 3
        if a[m1] < a[m2]:
            lo = m1 + 1                                # peak is right of m1
        else:
            hi = m2 - 1                                # peak is left of m2
    return max(range(lo, hi + 1), key=lambda i: a[i])


def subset_sums(xs: list[int]) -> list[int]:
    sums = [0]
    for x in xs:
        sums += [s + x for s in sums]
    return sums


def count_subsets_with_sum(nums: list[int], target: int) -> int:
    half = len(nums) // 2
    left = subset_sums(nums[:half])
    right = sorted(subset_sums(nums[half:]))
    return sum(bisect_right(right, target - s) - bisect_left(right, target - s) for s in left)


def lcg_values(n: int, seed: int = 42) -> list[int]:
    x, out = seed, []
    for _ in range(n):
        x = (x * 48271) % 2147483647
        out.append(x % 1000 + 1)
    return out


if __name__ == "__main__":
    primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53]
    assert exponential_search(primes, 37) == 11 and exponential_search(primes, 2) == 0
    assert exponential_search(primes, 53) == 15 and exponential_search(primes, 4) == -1
    assert exponential_search(primes, 100) == -1 and exponential_search([], 1) == -1

    tens = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
    assert interpolation_search(tens, 70) == 6 and interpolation_search(tens, 55) == -1
    powers = [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024]
    assert interpolation_search(powers, 256) == 8 and interpolation_search(powers, 1) == 0
    assert interpolation_search([5, 5, 5], 5) == 0 and interpolation_search([], 3) == -1
    skewed = list(range(1, 1000)) + [10**12]
    assert interpolation_search(skewed, 999) == 998

    assert ternary_max_index([1, 3, 8, 12, 15, 14, 9, 4, 2]) == 4
    assert ternary_max_index([5, 4, 3]) == 0 and ternary_max_index([1, 2, 3, 4]) == 3

    assert count_subsets_with_sum([3, 34, 4, 12, 5, 2], 9) == 2
    nums = lcg_values(20)
    assert nums[:3] == [383, 408, 38] and sum(nums) == 10965
    assert count_subsets_with_sum(nums, 5000) == 259          # DP gives 259
    assert count_subsets_with_sum(nums, 1000) == 1
    assert count_subsets_with_sum(nums, 0) == 1               # the empty subset
    assert count_subsets_with_sum(nums, 10965) == 1 and count_subsets_with_sum(nums, 10966) == 0
    print("ok")
import java.util.Arrays;

public class OtherSearches {
    static int exponentialSearch(int[] a, int t) {
        int n = a.length;
        if (n == 0) return -1;
        if (a[0] >= t) return a[0] == t ? 0 : -1;
        int bound = 1;
        while (bound < n && a[bound] < t) bound *= 2;
        int lo = bound / 2 + 1, hi = Math.min(bound, n - 1) + 1;   // half-open [lo, hi)
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (a[mid] >= t) hi = mid; else lo = mid + 1;
        }
        return lo < n && a[lo] == t ? lo : -1;
    }

    static int interpolationSearch(long[] a, long t) {
        int lo = 0, hi = a.length - 1;
        while (lo <= hi && a[lo] <= t && t <= a[hi]) {
            if (a[hi] == a[lo]) return a[lo] == t ? lo : -1;
            // (t - a[lo]) * (hi - lo) can exceed 2^63 for huge keys: interpolate in double
            int pos = lo + (int) ((double) (t - a[lo]) / (double) (a[hi] - a[lo]) * (hi - lo));
            pos = Math.max(lo, Math.min(hi, pos));
            if (a[pos] == t) return pos;
            if (a[pos] < t) lo = pos + 1; else hi = pos - 1;
        }
        return -1;
    }

    static int ternaryMaxIndex(int[] a) {
        int lo = 0, hi = a.length - 1;
        while (hi - lo > 2) {
            int m1 = lo + (hi - lo) / 3, m2 = hi - (hi - lo) / 3;
            if (a[m1] < a[m2]) lo = m1 + 1; else hi = m2 - 1;
        }
        int best = lo;
        for (int i = lo + 1; i <= hi; i++) if (a[i] > a[best]) best = i;
        return best;
    }

    static long[] subsetSums(int[] xs, int from, int to) {
        long[] sums = new long[1 << (to - from)];
        int size = 1;                                   // sums[0] = 0
        for (int k = from; k < to; k++) {
            for (int j = 0; j < size; j++) sums[size + j] = sums[j] + xs[k];
            size *= 2;
        }
        return sums;
    }

    static int lowerBound(long[] a, long x) {
        int lo = 0, hi = a.length;
        while (lo < hi) { int m = lo + (hi - lo) / 2; if (a[m] >= x) hi = m; else lo = m + 1; }
        return lo;
    }

    static long countSubsetsWithSum(int[] nums, long target) {
        int half = nums.length / 2;
        long[] left = subsetSums(nums, 0, half);
        long[] right = subsetSums(nums, half, nums.length);
        Arrays.sort(right);
        long count = 0;
        for (long s : left) count += lowerBound(right, target - s + 1) - lowerBound(right, target - s);
        return count;
    }

    static int[] lcgValues(int n, long seed) {
        int[] out = new int[n];
        long x = seed;
        for (int i = 0; i < n; i++) { x = (x * 48271L) % 2147483647L; out[i] = (int) (x % 1000) + 1; }
        return out;
    }

    static void check(boolean ok, String what) { if (!ok) throw new AssertionError(what); }

    public static void main(String[] args) {
        int[] primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53};
        check(exponentialSearch(primes, 37) == 11 && exponentialSearch(primes, 2) == 0, "exp 1");
        check(exponentialSearch(primes, 53) == 15 && exponentialSearch(primes, 4) == -1, "exp 2");
        check(exponentialSearch(primes, 100) == -1 && exponentialSearch(new int[0], 1) == -1, "exp 3");

        long[] tens = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
        check(interpolationSearch(tens, 70) == 6 && interpolationSearch(tens, 55) == -1, "interp 1");
        long[] powers = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024};
        check(interpolationSearch(powers, 256) == 8 && interpolationSearch(powers, 1) == 0, "interp 2");
        check(interpolationSearch(new long[]{5, 5, 5}, 5) == 0 && interpolationSearch(new long[0], 3) == -1, "interp 3");
        long[] skewed = new long[1000];
        for (int i = 0; i < 999; i++) skewed[i] = i + 1;
        skewed[999] = 1_000_000_000_000L;
        check(interpolationSearch(skewed, 999) == 998, "interp skewed");

        check(ternaryMaxIndex(new int[]{1, 3, 8, 12, 15, 14, 9, 4, 2}) == 4, "ternary 1");
        check(ternaryMaxIndex(new int[]{5, 4, 3}) == 0 && ternaryMaxIndex(new int[]{1, 2, 3, 4}) == 3, "ternary 2");

        check(countSubsetsWithSum(new int[]{3, 34, 4, 12, 5, 2}, 9) == 2, "mitm small");
        int[] nums = lcgValues(20, 42);
        check(nums[0] == 383 && nums[1] == 408 && nums[2] == 38 && Arrays.stream(nums).sum() == 10965, "lcg");
        check(countSubsetsWithSum(nums, 5000) == 259, "mitm 5000");
        check(countSubsetsWithSum(nums, 1000) == 1 && countSubsetsWithSum(nums, 0) == 1, "mitm edges");
        check(countSubsetsWithSum(nums, 10965) == 1 && countSubsetsWithSum(nums, 10966) == 0, "mitm total");
        System.out.println("ok");
    }
}
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <iostream>
#include <numeric>
#include <vector>

int exponential_search(const std::vector<int>& a, int t) {
    int n = static_cast<int>(a.size());
    if (n == 0) return -1;
    if (a[0] >= t) return a[0] == t ? 0 : -1;
    int bound = 1;
    while (bound < n && a[bound] < t) bound *= 2;
    auto first = a.begin() + (bound / 2 + 1);
    auto last = a.begin() + (std::min(bound, n - 1) + 1);
    auto it = std::lower_bound(first, last, t);
    return (it != a.end() && *it == t) ? static_cast<int>(it - a.begin()) : -1;
}

int interpolation_search(const std::vector<std::int64_t>& a, std::int64_t t) {
    int lo = 0, hi = static_cast<int>(a.size()) - 1;
    while (lo <= hi && a[lo] <= t && t <= a[hi]) {
        if (a[hi] == a[lo]) return a[lo] == t ? lo : -1;
        double frac = static_cast<double>(t - a[lo]) / static_cast<double>(a[hi] - a[lo]);
        int pos = lo + static_cast<int>(frac * (hi - lo));
        pos = std::clamp(pos, lo, hi);
        if (a[pos] == t) return pos;
        if (a[pos] < t) lo = pos + 1; else hi = pos - 1;
    }
    return -1;
}

int ternary_max_index(const std::vector<int>& a) {
    int lo = 0, hi = static_cast<int>(a.size()) - 1;
    while (hi - lo > 2) {
        int m1 = lo + (hi - lo) / 3, m2 = hi - (hi - lo) / 3;
        if (a[m1] < a[m2]) lo = m1 + 1; else hi = m2 - 1;
    }
    return static_cast<int>(std::max_element(a.begin() + lo, a.begin() + hi + 1) - a.begin());
}

std::vector<std::int64_t> subset_sums(const std::vector<int>& xs, std::size_t from, std::size_t to) {
    std::vector<std::int64_t> sums{0};
    for (std::size_t k = from; k < to; ++k) {
        std::size_t size = sums.size();
        for (std::size_t j = 0; j < size; ++j) sums.push_back(sums[j] + xs[k]);
    }
    return sums;
}

std::int64_t count_subsets_with_sum(const std::vector<int>& nums, std::int64_t target) {
    std::size_t half = nums.size() / 2;
    auto left = subset_sums(nums, 0, half);
    auto right = subset_sums(nums, half, nums.size());
    std::sort(right.begin(), right.end());
    std::int64_t count = 0;
    for (std::int64_t s : left) {
        auto [lo, hi] = std::equal_range(right.begin(), right.end(), target - s);
        count += hi - lo;
    }
    return count;
}

std::vector<int> lcg_values(int n, std::int64_t seed = 42) {
    std::vector<int> out;
    std::int64_t x = seed;
    for (int i = 0; i < n; ++i) {
        x = (x * 48271) % 2147483647;
        out.push_back(static_cast<int>(x % 1000) + 1);
    }
    return out;
}

int main() {
    std::vector<int> primes{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53};
    assert(exponential_search(primes, 37) == 11 && exponential_search(primes, 2) == 0);
    assert(exponential_search(primes, 53) == 15 && exponential_search(primes, 4) == -1);
    assert(exponential_search(primes, 100) == -1 && exponential_search({}, 1) == -1);

    std::vector<std::int64_t> tens{10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
    assert(interpolation_search(tens, 70) == 6 && interpolation_search(tens, 55) == -1);
    std::vector<std::int64_t> powers{1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024};
    assert(interpolation_search(powers, 256) == 8 && interpolation_search(powers, 1) == 0);
    assert(interpolation_search({5, 5, 5}, 5) == 0 && interpolation_search({}, 3) == -1);
    std::vector<std::int64_t> skewed(999);
    std::iota(skewed.begin(), skewed.end(), 1);
    skewed.push_back(1000000000000LL);
    assert(interpolation_search(skewed, 999) == 998);

    assert(ternary_max_index({1, 3, 8, 12, 15, 14, 9, 4, 2}) == 4);
    assert(ternary_max_index({5, 4, 3}) == 0 && ternary_max_index({1, 2, 3, 4}) == 3);

    assert(count_subsets_with_sum({3, 34, 4, 12, 5, 2}, 9) == 2);
    auto nums = lcg_values(20);
    assert(nums[0] == 383 && nums[1] == 408 && nums[2] == 38);
    assert(std::accumulate(nums.begin(), nums.end(), 0) == 10965);
    assert(count_subsets_with_sum(nums, 5000) == 259);
    assert(count_subsets_with_sum(nums, 1000) == 1 && count_subsets_with_sum(nums, 0) == 1);
    assert(count_subsets_with_sum(nums, 10965) == 1 && count_subsets_with_sum(nums, 10966) == 0);
    std::cout << "ok\n";
}
function lowerBound(a: number[], x: number, lo = 0, hi = a.length): number {
  while (lo < hi) {
    const m = lo + Math.floor((hi - lo) / 2);
    if (a[m] >= x) hi = m; else lo = m + 1;
  }
  return lo;
}

function exponentialSearch(a: number[], t: number): number {
  const n = a.length;
  if (n === 0) return -1;
  if (a[0] >= t) return a[0] === t ? 0 : -1;
  let bound = 1;
  while (bound < n && a[bound] < t) bound *= 2;
  const i = lowerBound(a, t, Math.floor(bound / 2) + 1, Math.min(bound, n - 1) + 1);
  return i < n && a[i] === t ? i : -1;
}

function interpolationSearch(a: number[], t: number): number {
  let lo = 0, hi = a.length - 1;
  while (lo <= hi && a[lo] <= t && t <= a[hi]) {
    if (a[hi] === a[lo]) return a[lo] === t ? lo : -1;
    let pos = lo + Math.floor(((t - a[lo]) / (a[hi] - a[lo])) * (hi - lo));
    pos = Math.max(lo, Math.min(hi, pos));
    if (a[pos] === t) return pos;
    if (a[pos] < t) lo = pos + 1; else hi = pos - 1;
  }
  return -1;
}

function ternaryMaxIndex(a: number[]): number {
  let lo = 0, hi = a.length - 1;
  while (hi - lo > 2) {
    const m1 = lo + Math.floor((hi - lo) / 3), m2 = hi - Math.floor((hi - lo) / 3);
    if (a[m1] < a[m2]) lo = m1 + 1; else hi = m2 - 1;
  }
  let best = lo;
  for (let i = lo + 1; i <= hi; i++) if (a[i] > a[best]) best = i;
  return best;
}

function subsetSums(xs: number[]): number[] {
  let sums = [0];
  for (const x of xs) sums = sums.concat(sums.map((s) => s + x));
  return sums;
}

function countSubsetsWithSum(nums: number[], target: number): number {
  const half = Math.floor(nums.length / 2);
  const left = subsetSums(nums.slice(0, half));
  const right = subsetSums(nums.slice(half)).sort((p, q) => p - q);
  let count = 0;
  for (const s of left) count += lowerBound(right, target - s + 1) - lowerBound(right, target - s);
  return count;
}

function lcgValues(n: number, seed = 42): number[] {
  let x = seed;
  const out: number[] = [];
  for (let i = 0; i < n; i++) {
    x = (x * 48271) % 2147483647;
    out.push((x % 1000) + 1);
  }
  return out;
}

function assert(cond: boolean, what: string): void {
  if (!cond) throw new Error("assertion failed: " + what);
}

const primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53];
assert(exponentialSearch(primes, 37) === 11 && exponentialSearch(primes, 2) === 0, "exp 1");
assert(exponentialSearch(primes, 53) === 15 && exponentialSearch(primes, 4) === -1, "exp 2");
assert(exponentialSearch(primes, 100) === -1 && exponentialSearch([], 1) === -1, "exp 3");

const tens = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100];
assert(interpolationSearch(tens, 70) === 6 && interpolationSearch(tens, 55) === -1, "interp 1");
const powers = [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024];
assert(interpolationSearch(powers, 256) === 8 && interpolationSearch(powers, 1) === 0, "interp 2");
assert(interpolationSearch([5, 5, 5], 5) === 0 && interpolationSearch([], 3) === -1, "interp 3");
const skewed = Array.from({ length: 999 }, (_, i) => i + 1).concat([1e12]);
assert(interpolationSearch(skewed, 999) === 998, "interp skewed");

assert(ternaryMaxIndex([1, 3, 8, 12, 15, 14, 9, 4, 2]) === 4, "ternary 1");
assert(ternaryMaxIndex([5, 4, 3]) === 0 && ternaryMaxIndex([1, 2, 3, 4]) === 3, "ternary 2");

assert(countSubsetsWithSum([3, 34, 4, 12, 5, 2], 9) === 2, "mitm small");
const nums = lcgValues(20);
assert(nums[0] === 383 && nums[1] === 408 && nums[2] === 38, "lcg");
assert(nums.reduce((s, v) => s + v, 0) === 10965, "lcg sum");
assert(countSubsetsWithSum(nums, 5000) === 259, "mitm 5000");
assert(countSubsetsWithSum(nums, 1000) === 1 && countSubsetsWithSum(nums, 0) === 1, "mitm edges");
assert(countSubsetsWithSum(nums, 10965) === 1 && countSubsetsWithSum(nums, 10966) === 0, "mitm total");
console.log("ok");

Variants: golden-section search, jump search, Fibonacci search, and MITM at

import bisect
import math
import random


def golden_section_min(f, lo: float, hi: float, iters: int = 100) -> float:
    inv_phi = (math.sqrt(5) - 1) / 2                 # 0.618...
    x1, x2 = hi - inv_phi * (hi - lo), lo + inv_phi * (hi - lo)
    f1, f2 = f(x1), f(x2)
    for _ in range(iters):                           # one new evaluation per iteration
        if f1 < f2:
            hi, x2, f2 = x2, x1, f1
            x1 = hi - inv_phi * (hi - lo)
            f1 = f(x1)
        else:
            lo, x1, f1 = x1, x2, f2
            x2 = lo + inv_phi * (hi - lo)
            f2 = f(x2)
    return (lo + hi) / 2


def jump_search(a: list[int], t: int) -> tuple[int, int]:
    n, comparisons = len(a), 0
    step = max(1, math.isqrt(n))
    prev, i = 0, step
    while i < n:                                     # check the last element of each block
        comparisons += 1
        if a[i - 1] >= t:
            break
        prev, i = i, i + step
    for j in range(prev, min(i, n)):                 # linear scan inside the block
        comparisons += 1
        if a[j] == t:
            return j, comparisons
    return -1, comparisons


def fibonacci_search(a: list[int], t: int) -> int:
    n = len(a)
    f2, f1 = 0, 1
    f = f1 + f2
    while f < n:
        f2, f1 = f1, f
        f = f1 + f2
    offset = -1
    while f > 1:
        i = min(offset + f2, n - 1)
        if a[i] < t:
            f, f1 = f1, f2
            f2 = f - f1
            offset = i
        elif a[i] > t:
            f = f2
            f1 = f1 - f2
            f2 = f - f1
        else:
            return i
    if f1 and offset + 1 < n and a[offset + 1] == t:
        return offset + 1
    return -1


def count_subsets_mitm(nums: list[int], target: int) -> int:
    def sums(xs):
        out = [0]
        for x in xs:
            out += [s + x for s in out]
        return out
    half = len(nums) // 2
    left, right = sums(nums[:half]), sorted(sums(nums[half:]))
    return sum(bisect.bisect_right(right, target - s) - bisect.bisect_left(right, target - s) for s in left)


assert abs(golden_section_min(lambda x: (x - 2) ** 2 + 1, 0.0, 7.0) - 2.0) < 1e-6

evens = list(range(0, 200, 2))
assert jump_search(evens, 150) == (75, 14) and jump_search(evens, 151)[0] == -1

fib_arr = [10, 22, 35, 40, 45, 50, 80, 82, 85, 90, 100]
assert all(fibonacci_search(fib_arr, x) == i for i, x in enumerate(fib_arr))
assert fibonacci_search(fib_arr, 36) == -1 and fibonacci_search(fib_arr, 101) == -1

random.seed(3)
big = [random.randrange(10**11, 10**12) for _ in range(40)]   # far too large for a DP over sums
target = sum(big[::3])                                        # a subset that certainly exists
assert count_subsets_mitm(big, target) >= 1                   # 2 * 2^20 sums instead of 2^40 subsets
print("ok")

Real-world uses

Numerical optimisation and tuning. Golden-section search is the textbook line search for one-dimensional minimisation without derivatives, and Brent's method (SciPy's minimize_scalar(method="brent"), the default) combines it with parabolic interpolation. Engineers use the same idea informally to tune a single knob whose cost curve is U-shaped: thread-pool size against throughput, batch size against latency, cache size against hit rate and memory cost (see Cache Sizing Math). The danger is the same as in theory — real cost curves are noisy and have plateaus, so ternary search on raw measurements needs repeated trials or a coarser grid.

Galloping inside sorts and merges. Timsort (Python, Java objects, V8) and its descendants gallop during merges; merge-join style intersections use the same exponential search to skip long stretches of non-matching keys. Search engines intersect posting lists with galloping: to intersect a short list with a long one, gallop through the long list from the current position for each element of the short one — instead of (Demaine, López-Ortiz and Munro, "Adaptive set intersections, unions, and differences", SODA 2000). See Search Engineering.

Interpolation search and learned indexes. Interpolation search is rarely used raw, but its idea — predict the position from the key — is the core of learned indexes (Kraska et al., "The Case for Learned Index Structures", SIGMOD 2018): a small model maps a key to an approximate position with a bounded error, followed by a local search. Production descendants such as RadixSpline and PGM-index appear in research systems and some databases. The same "guess the slot from the value" logic underlies searching sorted, evenly distributed keys like timestamps in time-series files or hashed IDs; see Indexing Deep Dive.

Two-level indexes everywhere. Jump search's "index the block heads, then scan one block" is the structure of SSTable index blocks, Kafka's sparse offset index, Parquet row-group statistics, and the root levels of B-trees (Storage Engines).

Meet-in-the-middle in security. The 2DES attack (Diffie and Hellman, 1977) is why 3DES uses three stages; generic meet-in-the-middle and baby-step giant-step attacks set minimum parameter sizes for discrete-log cryptography; rainbow tables are a related time–memory trade-off for password hashes (see Hashing Algorithms and Cryptography for Engineers).

Bidirectional search in routing and puzzles. Route planners run bidirectional Dijkstra or A* between source and destination, and social-network "degrees of separation" features meet in the middle. Puzzle solvers (Rubik's cube optimal solvers, sliding puzzles) combine bidirectional search with pattern databases.

Pitfalls & edge cases

  • Ternary search on non-strict unimodal functions. Plateaus make ties uninformative and the search can discard the optimum. Check strictness, or switch to a method that tolerates plateaus (a grid scan plus local refinement).
  • Ternary search on integer ranges. Loops like while lo < hi with can stall when (both midpoints coincide with endpoints). Stop when the range has at most three elements and scan, or use binary search on f(m) < f(m+1).
  • Floating-point loops. As with binary search, use a fixed iteration count (100 for ternary, 200 is plenty for golden section) instead of while hi - lo > eps.
  • Convex vs unimodal. Convex functions are unimodal (for minimisation) only if strictly convex or if flat minima are acceptable — a flat bottom is fine (any point on it is optimal) but a flat shoulder above the optimum is not.
  • Exponential search off-by-one. Searching but forgetting to clamp bound to reads past the end; forgetting to check a[0] first misses a target at index 0.
  • Interpolation division by zero when a[lo] == a[hi] (duplicates); overflow in (t - a[lo]) * (hi - lo) for large keys in 64-bit languages (use 128-bit arithmetic or doubles with clamping); non-numeric keys (strings need a mapping to numbers, e.g. the first 8 bytes as an integer).
  • Interpolation on skewed data. Exponential, Zipfian or clustered keys can make it linear. Use an interpolation–binary hybrid if you do not control the data.
  • Meet-in-the-middle memory. 64-bit sums are 8 MB; are 256 MB. Python lists of ints use about 4–5× more (boxed integers). Estimate before you allocate.
  • Counting vs existence. When counting, keep duplicate sums in the sorted half and count with upper_bound - lower_bound; deduplicating gives wrong counts. When the empty subset should not count, subtract it.
  • Odd . Split as and ; the bigger half dominates the cost.
  • Closest sum, not exact. For "closest to ", for each left sum find the predecessor and successor of in the sorted right sums — two candidates, not one.

Variations

  • Binary search on the slope — the integer-domain replacement for ternary search; see Binary Search Mastery.
  • Brent's method and parabolic interpolation — faster convergence than golden section on smooth functions, with golden section as a safeguard.
  • Interpolation–binary hybrids, interpolation-sequential search — worst-case guarantees with near- typical cost.
  • Learned indexes — interpolation with a trained model; a modern research area.
  • Exponential search from the end / "doubling" on answers — finding an upper bound for search on the answer when no bound is given: try until feasible.
  • Schroeppel–Shamir — meet-in-the-middle in time with memory using heaps over four quarters.
  • Bidirectional BFS / Dijkstra / A* — meet-in-the-middle on graphs, in the graph module.
  • Baby-step giant-step — discrete logarithm, number-theory module.
  • Sqrt decomposition — the block idea applied to range queries; see Sparse Tables & Sqrt Decomposition.

Practice ladder

Easy → hard. Descriptions are paraphrased; follow the links for exact statements.

1. Peak Index in a Mountain Array (LeetCode 852) — find the peak of a strictly increasing-then-decreasing array. Teaches ternary search and why binary search on the slope is simpler.

Hint

Binary search for the first i with a[i] > a[i+1].

Solution
def peak_index(arr: list[int]) -> int:
    lo, hi = 0, len(arr) - 1           # first i with arr[i] > arr[i + 1]; the last index is always "true"
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] > arr[mid + 1]:
            hi = mid
        else:
            lo = mid + 1
    return lo


def peak_index_ternary(arr: list[int]) -> int:
    lo, hi = 0, len(arr) - 1
    while hi - lo > 2:
        m1, m2 = lo + (hi - lo) // 3, hi - (hi - lo) // 3
        if arr[m1] < arr[m2]:
            lo = m1 + 1
        else:
            hi = m2 - 1
    return max(range(lo, hi + 1), key=arr.__getitem__)


for arr, want in [([0, 1, 0], 1), ([0, 2, 1, 0], 1), ([0, 10, 5, 2], 1), ([1, 3, 8, 12, 15, 14, 9, 4, 2], 4)]:
    assert peak_index(arr) == want and peak_index_ternary(arr) == want
print("ok")

Both ; the binary version makes comparisons, the ternary version about .

2. Search in a Sorted Array of Unknown Size (LeetCode 702) (premium) — sorted array behind a reader that returns a sentinel out of range. Teaches exponential search.

Hint

Double hi while reader.get(hi) < target, then binary search . The sentinel is larger than every value, so it behaves like .

3. Find in Mountain Array (LeetCode 1095) — the smallest index of a target in a mountain array with a limited number of reads. Teaches composing searches: peak first, then an ascending and a descending binary search.

Hint

Three binary searches: peak; lower_bound on the increasing part; a reversed comparison on the decreasing part. About reads.

4. 4Sum II (LeetCode 454) — count index tuples across four arrays summing to zero. Teaches meet-in-the-middle with a hash map.

Hint

Count all a + b in a map; for each c + d, add count[-(c + d)].

Solution
from collections import Counter


def four_sum_count(a: list[int], b: list[int], c: list[int], d: list[int]) -> int:
    ab = Counter(x + y for x in a for y in b)
    return sum(ab[-(x + y)] for x in c for y in d)


assert four_sum_count([1, 2], [-2, -1], [-1, 2], [0, 2]) == 2
assert four_sum_count([0], [0], [0], [0]) == 1
assert four_sum_count([1], [1], [1], [1]) == 0
print("ok")

expected time and space, against brute force; for that is 80,000 map operations instead of tuples.

5. Sum of Four Values (CSES 1642) — find four distinct positions whose values sum to . Teaches meet-in-the-middle on pairs with the distinct-index constraint.

Hint

Treat index as a split point. For each : first, for every , look up in a hash map of pair sums with ; then insert every pair with into the map. Every pair in the map ends before , so the four indices are distinct. expected.

6. Minimum Cost to Make Array Equal (LeetCode 2448) — choose a target value minimising weighted distance cost. Teaches ternary search on a convex integer function (or binary search on the slope; the exact answer is a weighted median).

Hint

cost(x) = sum(cost_i * |nums_i - x|) is convex in . Binary search for the first with cost(x) <= cost(x + 1).

7. Best Position for a Service Centre (LeetCode 1515) — the point minimising the sum of Euclidean distances. Teaches nested ternary search on a convex function of two variables.

Hint

The sum of distances is convex in . Ternary search ; inside, ternary search for that . 100 × 100 iterations of an evaluation is fine for .

8. Weakness and Poorness (Codeforces 578C) — choose to minimise the maximum absolute subarray sum of . Teaches ternary search over reals where each evaluation is itself an algorithm (Kadane's) and the function is convex.

Hint

The "weakness" as a function of is a maximum of convex (linear-in- absolute) functions, hence convex. Ternary search with ~100 iterations, each running max/min subarray sum.

9. Meet in the Middle (CSES 1628) — count subsets of up to 40 numbers (values up to ) with sum . Teaches the canonical MITM, with attention to speed.

Hint

Generate both halves' sums sorted by merging, then count with two pointers walking in opposite directions, grouping equal values.

Solution
def sorted_subset_sums(xs: list[int]) -> list[int]:
    sums = [0]
    for x in xs:                       # merge sums with sums + x: stays sorted, O(2^k) per item
        shifted = [s + x for s in sums]
        merged, i, j = [], 0, 0
        while i < len(sums) or j < len(shifted):
            if j == len(shifted) or (i < len(sums) and sums[i] <= shifted[j]):
                merged.append(sums[i]); i += 1
            else:
                merged.append(shifted[j]); j += 1
        sums = merged
    return sums


def count_subsets(nums: list[int], x: int) -> int:
    half = len(nums) // 2
    left, right = sorted_subset_sums(nums[:half]), sorted_subset_sums(nums[half:])
    i, j, count = 0, len(right) - 1, 0
    while i < len(left) and j >= 0:
        s = left[i] + right[j]
        if s < x:
            i += 1
        elif s > x:
            j -= 1
        else:                          # count equal runs on both sides
            a = left[i]; ca = 0
            while i < len(left) and left[i] == a:
                i += 1; ca += 1
            b = right[j]; cb = 0
            while j >= 0 and right[j] == b:
                j -= 1; cb += 1
            count += ca * cb
    return count


assert count_subsets([2, 4, 1, 2], 5) == 2
assert count_subsets([3, 34, 4, 12, 5, 2], 9) == 2
assert count_subsets([1, 1, 1, 1], 2) == 6
assert count_subsets([5], 5) == 1 and count_subsets([5], 4) == 0
print("ok")

time and memory. For in a compiled language this runs in well under a second; in Python it is borderline and benefits from NumPy.

10. Closest Subsequence Sum (LeetCode 1755) — choose a subset (by index) minimising , , values up to in magnitude. Teaches MITM for "closest", with predecessor and successor lookups.

Hint

Sort right sums; for each left sum , check the elements just at and before lower_bound(goal - s).

Solution
from bisect import bisect_left


def min_abs_difference(nums: list[int], goal: int) -> int:
    def sums(xs):
        out = [0]
        for x in xs:
            out += [s + x for s in out]
        return out

    half = len(nums) // 2
    left, right = sums(nums[:half]), sorted(set(sums(nums[half:])))
    best = abs(goal)                               # the empty subset
    for s in left:
        i = bisect_left(right, goal - s)
        if i < len(right):
            best = min(best, abs(s + right[i] - goal))
        if i > 0:
            best = min(best, abs(s + right[i - 1] - goal))
        if best == 0:
            break
    return best


assert min_abs_difference([5, -7, 3, 5], 6) == 0
assert min_abs_difference([7, -9, 15, -2], -5) == 1
assert min_abs_difference([1, 2, 3], -7) == 7
print("ok")

time, space. Deduplicating the right half is safe here (we need closeness, not counts) — unlike the counting problem.

11. Partition Array Into Two Arrays to Minimize Sum Difference (LeetCode 2035) — split numbers () into two equal-size halves with minimal sum difference. Teaches MITM grouped by subset size.

Hint

For each half, group subset sums by how many elements were chosen. A choice of from the left must pair with from the right; within each group, binary search for the sum closest to .

12. Split Array With Same Average (LeetCode 805) — can the array be split into two non-empty parts with equal averages? Teaches reducing to a subset-sum condition and applying MITM by size.

Hint

Subtract the mean (scale by to keep integers): you need a non-empty proper subset summing to 0. MITM on sums with sets; exclude the "take everything" case.

13. Word Ladder (LeetCode 127) — shortest transformation sequence between two words. Teaches bidirectional BFS: expand the smaller frontier each time and stop when they meet.

Hint

Two sets, front and back; always expand the smaller; a word in the other set ends the search. Same answer as BFS, far fewer visited words.

Common mistakes & interview follow-ups

"Why not ternary search instead of binary search on a sorted array?" It is never better for a monotone predicate: two comparisons to shrink by 2/3 versus one to shrink by 1/2 — about 1.7× more comparisons. Ternary search is for unimodal functions, where binary search on values does not apply.

"Your function has a plateau — does ternary still work?" Only if the plateau is at the optimum. Otherwise ties are uninformative and the search can discard the optimum. Use binary search on a strict slope predicate, add a tie-breaker, or scan a grid.

"The array is infinite / you can't get its length." Exponential search; mention the bound and that it is what Timsort uses during merges.

"When would you use interpolation search in practice?" When keys are numeric and close to uniform and probes are expensive (disk pages, remote reads). Mention the worst case and the hybrid fix, and learned indexes as the modern form.

"Subset sum with and values up to ?" Meet-in-the-middle: sums per half, sort one, binary search or two-pointer. State memory (8 MB per half) and that DP over sums is impossible at this value range.

"What if ?" sums per half is 8 GB — too much. Schroeppel–Shamir keeps time but needs only memory — about entries per quarter; or exploit structure (small values → DP; approximate answer → FPTAS).

"How does bidirectional BFS help, and when doesn't it?" It turns into about explored nodes, but needs a known target, a way to generate predecessors, and a correct meeting condition (finish the current layer before declaring the shortest distance). It doesn't help for single-source all-targets problems.

Quick quiz

1. Why does ternary search need two interior evaluations per step, while binary search needs one?

Answer

Binary search tests a monotone predicate whose value at one point says which side the boundary is on. For a unimodal function, one value cannot tell whether the point is left or right of the peak; comparing two values and does — the side with the smaller value cannot contain the maximum beyond its own point.

2. Golden-section search shrinks the interval by 0.618 per evaluation and ternary search by about 0.816. How many evaluations does each need to shrink an interval by a factor of ?

Answer

Golden section: evaluations (plus one initial). Ternary: iterations, i.e. 70 evaluations.

3. On what input does interpolation search take probes, and why?

Answer

Keys like [1, 2, …, n-1, 10^12] searching for : the enormous last key makes the interpolated position round down to every time, so each probe eliminates only one element. The bound assumes keys spread roughly uniformly between the endpoints.

4. Exponential search finds a target at position in how many probes, and why is that useful inside Timsort?

Answer

About doubling probes plus a binary search over fewer than elements: , at most about . In a merge, the next element of one run often belongs far ahead in the other run; galloping from the current position finds that spot in time logarithmic in the distance, so merging runs that barely interleave costs instead of .

5. Meet-in-the-middle for counting subsets with sum : why must duplicate sums be kept in the sorted half, and what goes wrong if you use a set?

Answer

Each entry in the right-half list represents one distinct subset. Two different subsets can have the same sum, and each pairs with every matching left subset to form a distinct full subset. A set collapses them, undercounting: for [1, 1, 1, 1] and the answer is 6, but deduplicated halves (left , right ) give only 3.

Further reading / sources

  • J. Kiefer, "Sequential minimax search for a maximum", Proceedings of the American Mathematical Society 4(3), 1953 — Fibonacci and golden-section search.
  • Yehoshua Perl, Alon Itai and Haim Avni, "Interpolation search — a log log N search", Communications of the ACM 21(7), 1978.
  • Andrew C. Yao and F. Frances Yao, "The complexity of searching an ordered random table", FOCS 1976.
  • Jon L. Bentley and Andrew C. Yao, "An almost optimal algorithm for unbounded searching", Information Processing Letters 5(3), 1976.
  • Donald E. Knuth, The Art of Computer Programming, Vol. 3, 2nd ed., §6.2.1 — Fibonaccian search, interpolation search, and their analyses.
  • Whitfield Diffie and Martin E. Hellman, "Exhaustive Cryptanalysis of the NBS Data Encryption Standard", Computer 10(6), 1977 — the meet-in-the-middle idea against multiple encryption.
  • Richard Schroeppel and Adi Shamir, "A , Algorithm for Certain NP-Complete Problems", SIAM Journal on Computing 10(3), 1981.
  • Erik D. Demaine, Alejandro López-Ortiz and J. Ian Munro, "Adaptive set intersections, unions, and differences", SODA 2000.
  • Tim Kraska, Alex Beutel, Ed H. Chi, Jeffrey Dean, Neoklis Polyzotis, "The Case for Learned Index Structures", SIGMOD 2018.
  • William H. Press et al., Numerical Recipes, 3rd ed., §10.2 (golden-section search) and §10.3 (Brent's method).
  • cp-algorithms, Ternary search.
  • Antti Laaksonen, Competitive Programmer's Handbook — the meet-in-the-middle section of the "Complete search" chapter.

Lessons: previous — Binary Search Mastery · next — Quickselect & Order Statistics · module — Searching & Sorting · course map.

Related Archon pages: Sorting in the Real World · Hash Tables · Graphs · Indexing Deep Dive · Search Engineering · Cryptography for Engineers · Sparse Tables & Sqrt Decomposition · Backtracking & Recursion.