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 9 when the array may be far longer than the part that matters. Probe indices 1, 2, 4, 8, ... until a value passes the target; the target then lies between the last two probes, and a binary search of just that range finishes it.
Check your understanding
The player pauses before each decision in this run and asks what happens next. Here are all 5, with their answers.
Index 1 holds 3, target 9. What next?
Answer: Double to 2. Keep doubling while the probed value is still below the target and inside the array.
Index 2 holds 4, target 9. What next?
Answer: Double to 4. Keep doubling while the probed value is still below the target and inside the array.
Index 4 holds 9, target 9. What next?
Answer: Binary search 2 to 4. Keep doubling while the probed value is still below the target and inside the array.
Middle value 7, target 9. What happens next?
Answer: Search right. Compare the middle with the target and keep the half that can still hold it.
Middle value 9, target 9. 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
Search for 9 when the array may be far longer than the part that matters. Probe indices 1, 2, 4, 8, ... until a value passes the target; the target then lies between the last two probes, and a binary search of just that range finishes it.
Exponential search for 9.
Index 1 holds 3, below 9: double the bound to 2.
Index 1 holds 3.
Index 2 holds 4, below 9: double the bound to 4.
Index 2 holds 4.
Index 4 holds 9, which reaches 9: stop doubling. The target lies between index 2, which was below it, and 4.
Index 4 holds 9.
The middle of 2 to 4 is index 3, holding 7.
Middle index 3 holds 7.
7 is below 9, so the answer can only be to the right: search 4 to 4.
The middle of 4 to 4 is index 4, holding 9.
Middle index 4 holds 9.
9 equals 9: found at index 4.
Found 9 at index 4 after 6 probes. Doubling took O(log i) steps to reach the answer's position i, and the binary search covered a range of size at most i, so the whole search is O(log i): it never depends on how long the array really is.
Found at index 4.
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