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.
Binary search as recursion: search(low, high) probes the middle of its range and, on a miss, calls itself on the half that can still hold 72. The calls label is the stack; it grows by one frame per halving and every frame simply returns what the one above it found.
Check your understanding
The player pauses before each decision in this run and asks what happens next. Here are all 3, with their answers.
Middle value 16, target 72. What happens next?
Answer: Search right. Compare the middle with the target and keep the half that can still hold it.
Middle value 56, target 72. What happens next?
Answer: Search right. Compare the middle with the target and keep the half that can still hold it.
Middle value 72, target 72. What happens next?
Answer: Found it. Compare the middle with the target and keep the half that can still hold it.
How it runs, step by step
Binary search as recursion: search(low, high) probes the middle of its range and, on a miss, calls itself on the half that can still hold 72. The calls label is the stack; it grows by one frame per halving and every frame simply returns what the one above it found.
Recursive binary search for 72.
Call search(0, 9), depth 1. The middle of 0 to 9 is index 4, holding 16.
Middle index 4 holds 16.
16 is below 72, so the answer can only be to the right: search 5 to 9. That is a new call on top of this one.
16 is below 72, so the answer can only be to the right: search 5 to 9.
Call search(5, 9), depth 2. The middle of 5 to 9 is index 7, holding 56.
Middle index 7 holds 56.
56 is below 72, so the answer can only be to the right: search 8 to 9. That is a new call on top of this one.
56 is below 72, so the answer can only be to the right: search 8 to 9.
Call search(8, 9), depth 3. The middle of 8 to 9 is index 8, holding 72.
Middle index 8 holds 72.
72 equals 72: found at index 8.
Found 72 at index 8 after 3 probes and a call stack 4 deep. Each call halves the range, so the depth is O(log n), and since the recursive call is the last thing each frame does, a compiler can turn it into the loop of the iterative version.
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