Module 38
Advanced Search and Divide & Conquer
Ternary search on unimodal functions, meet in the middle for 2⁴⁰ search spaces, splitting problems in half, and the closest pair of points.
Divide and conquer solves a problem by splitting it into independent parts, solving each, and combining the results: merge sort and quickselect (Module 15) are the classic examples. This module extends the idea in three directions.
Ternary search finds the peak of a function that rises then falls. Meet in the middle splits an exponential search into two halves of 2^(n/2) each and joins them with sorting or hashing, turning 2⁴⁰ into about 2 × 2²⁰. Geometric divide and conquer finds the closest pair of points in O(n log n). The problems practise each one, plus expression splitting and staircase search in a sorted matrix.
Best after: Binary Search, Sorting and Divide & Conquer
Where this shows up in real systems
- System Design · System 12.34 — Proximity Service (Nearby Places / Yelp) — Nearby search splits space into cells (geohash, quadtrees): divide and conquer on coordinates.
- System Design · Topic 13B.4 — Geospatial Indexing: Geohash, Quadtrees & H3 — Quadtrees and geohashes recursively divide the map, exactly like divide and conquer.
Part 1
Learn the ideas
- 38.1Ternary Search on Unimodal FunctionsIf a function increases then decreases, compare two inner points and throw away the third that can't contain the peak. On integer arrays, comparing mid with mid + 1 (binary search) does the same job faster.10 min
- 38.2Meet in the MiddleWhen n is around 40, 2ⁿ subsets are too many, but 2^(n/2) ≈ 10⁶ is fine. Enumerate each half separately, sort one side, and combine with binary search or a hash map.14 min
- 38.3Closest Pair of Points and Splitting ExpressionsSplit the points by x, solve both halves, then check only a thin strip around the split line. Expressions split at every operator, combining results from both sides.12 min
Part 2
Solve the problems
Work through them in order. Each one shows the pattern it teaches.
Search on the slope instead of a value.
Start at a corner where one move increases and the other decreases: each step discards a whole row or column.
Split at every operator and combine every left result with every right result.
Meet in the middle with a hash map: pair sums of two arrays against pair sums of the other two.
Meet in the middle: 2²⁰ sums per half, sort one, binary search from the other.
Meet in the middle grouped by how many items each half contributes.
Geometric divide and conquer with the strip argument.