Search Variants
Binary search is not the only way to exploit a sorted array. Jump search moves forward a block at a time and scans the block that overshoots, which costs about sqrt(n) probes but never has to move backwards. Exponential search doubles its probe index until it passes the target and binary searches the last gap, so the cost depends on where the answer is rather than how long the array is. Interpolation search guesses the position from the values themselves, the way you open a dictionary near the back for a word starting with T, and needs only about log log n probes when the values are spread evenly. Recursive binary search is the familiar halving written as calls, each frame handing back what the deeper one found. Ternary search probes two points per round and keeps a third of the range; it looks like an upgrade until the comparisons are counted, and it is really a tool for finding the peak of a unimodal function, not for sorted arrays.
Search for 90 by guessing where it should be. If the values grew evenly from 10 to 120, the target would sit at the matching fraction of the way along: that is the probe. Each miss narrows the range like binary search does, but the probe lands close on evenly spread data, about log log n probes instead of log n.
Check your understanding
The player pauses before the one decision in this run and asks what happens next. Here it is, with the answer.
The guess holds 90, target 90. What happens next?
Answer: Found it. A miss cuts the range on the side the target cannot be.
How it runs, step by step
Search for 90 by guessing where it should be. If the values grew evenly from 10 to 120, the target would sit at the matching fraction of the way along: that is the probe. Each miss narrows the range like binary search does, but the probe lands close on evenly spread data, about log log n probes instead of log n.
Interpolation search for 90.
Range 0 to 11 holds 10 to 120. 90 is 80 above the low end out of a spread of 110, so the guess is 0 + 80 x 11 / 110 = index 8, holding 90.
Probe index 8, holding 90.
90 equals 90: found at index 8.
Found 90 at index 8 after 1 probes. On uniformly spread values interpolation needs about log log n probes; on lopsided data, such as values that grow exponentially, its guesses land badly and it degrades to O(n), which is why binary search is the safer default.
Found at index 8.
Write it yourself
Define jumpSearch(values, target) and return the index of the target, or -1 when it is not there. It runs in your browser against this lesson's own 2 examples.
// Step forward in blocks until you pass the target, then walk back through the last block.function jumpSearch(values, target) { return -1;}
Remember
- Jump search: block size sqrt(n); jump while the block's last value is below the target, then scan one block.
- Exponential search: probe 1, 2, 4, 8, ... until the value passes the target, then binary search the last doubling: O(log i) for an answer at index i.
- Interpolation guesses the position from the values: log log n probes on even data, O(n) on lopsided. Ternary search's two probes cost 2 log3 n, about 26% more than binary search; keep it for unimodal peaks.
Topics covered
Where this is used
Language runtimesTimsort's galloping mode
Python's list.sort and Java's Arrays.sort for objects both run Timsort, which merges two sorted runs. When one run wins seven comparisons in a row it switches to galloping: exponential search from the current position to find where the next element belongs. The cost then depends on the distance jumped rather than the length of the run, so a merge where one run sits entirely below the other finishes in a handful of probes instead of n comparisons. CPython's listsort.txt puts a number on it: galloping out to index i costs about 2 log2(i) + 2 comparisons, which loses to plain one-pair-at-a-time merging for i below 6 and wins by more and more above it. That is why the switch waits for seven wins in a row instead of galloping from the start.
Search enginesSkipping inside an inverted index
Lucene stores a skip list over each term's posting list so that advance(target) can leap whole blocks of document ids rather than decoding every one. Intersecting a rare term with a common one then behaves exactly like jump search: leap forward on the skip entries, decode only the block that could hold the match, scan it. Decoding is the expensive step, so skipping blocks is what stops a two-term query from reading the entire posting list.
Numerical computingGolden-section search in SciPy
scipy.optimize.minimize_scalar with method='golden' narrows a bracket around the minimum of a unimodal function, which is the problem ternary search was actually built for: there is no target to compare against, so you compare two interior probes to each other and throw away the side that cannot hold the extremum. Golden-section placement is the refinement - put the probes at the golden ratio and one of them is still usable next round, so each iteration costs a single new evaluation instead of two. That is the difference between one simulation run per step and two.
DatabasesLearned index structures
The 2017 paper 'The Case for Learned Index Structures' replaces a B-tree's descent with a model that predicts where a key lives, then corrects with a small local search. Interpolation search is the one-line version of that model: a straight line fitted to the two ends of the range. The research simply fits a better curve to the actual key distribution, so the first guess lands close and the local search covers a handful of slots instead of a subtree.
Why it works this way
Why blocks of sqrt(n) in jump search, and why jump at all
The cost is two parts pulling against each other: about n/k jumps to find the block that overshoots, then up to k steps to scan it. A bigger block means fewer jumps and a longer scan, and n/k + k is smallest when k is sqrt(n), which gives roughly 2 sqrt(n) probes. That is much worse than log n, so jump search only earns its place when moving backwards is the expensive part: a forward-only cursor, a compressed block you would have to decode again, a disk where seeking back costs more than reading on.
Exponential search exists because binary search has to know where the end is
Binary search starts from high = n - 1, so it cannot run on a stream, an unbounded sequence, or an index you can only probe one slot at a time. Doubling finds a bound in about log i probes, and the moment a[bound] passes the target you know the answer lies between bound/2 and bound - a window of size bound/2, so the binary search that follows is also log i. Total cost is O(log i) where i is the answer's index, which beats O(log n) whenever the target sits near the front.
Interpolation search is log log n only if the data really is evenly spread
The guess is a straight line through (low, a[low]) and (high, a[high]). On uniform values it lands within a few slots and the expected cost is about log log n. On lopsided values such as 1, 2, 4, 8 up to 2^k the line keeps pointing near low, one element falls away per round, and the search degrades to O(n) - no better than scanning. Two arithmetic traps ride along: a[high] == a[low] divides by zero, which is why the code guards it, and (target - a[low]) * (high - low) can overflow a 32-bit int long before the array is large enough to need the search.
The recursive version is not O(1) space unless the tail call is eliminated
Each call keeps a frame holding low, high and mid, so plain recursion costs O(log n) stack where the loop costs nothing. The call here is in tail position - its result is returned untouched - so Kotlin's tailrec keyword, or a C compiler at -O2, turns it back into the loop and the space back to O(1). CPython does no such rewrite at all, so a recursive binary search written in Python really does grow the stack, though at about 30 frames for a billion elements it stays far under the default recursion limit of 1000.
Read more
- Jump searchWikipedia
- Exponential searchWikipedia
- Interpolation searchWikipedia
- Ternary searchcp-algorithms
- The Case for Learned Index StructuresarXiv