Cairn
guides · comparison, not a new algorithm

↩ back to Guides

Choosing a Search Algorithm

This site has twelve Searching entries now — Binary Search, Interpolation Search, Exponential Search, Jump Search, Fibonacci Search, Linear Search, Search in Rotated Sorted Array, Ternary Search, Golden-Section Search, Quickselect, Binary Search on Answer, and Saddleback Search — each built, verified, and explained on its own page. Eleven of the twelve search a one-dimensional array (or, for Binary Search on Answer, an implicit range of candidate answers). Of those eleven, seven answer the exact same question, "does this exact value exist in this data, and where." Six of those seven only answer it correctly once the data is properly ordered — five need a plain ascending sort, the sixth (Search in Rotated Sorted Array) needs a sorted array that's been rotated once instead; the seventh, Linear Search, needs no ordering assumption at all and is correct on anything, in exchange for giving that speed up entirely. Four more, Ternary Search, Golden-Section Search, Quickselect, and Binary Search on Answer, each answer a different question from the first seven — though Ternary Search and Golden-Section Search answer the very same one as each other, just at different per-step costs, so it's really three distinct questions split across four pages. The twelfth, Saddleback Search, doesn't fit either bucket — it answers the same "does this value exist" question as the first seven, just on a two-dimensional matrix instead of a one-dimensional array, a data shape none of the other eleven can even represent. This guide sorts the eleven one-dimensional entries by the actual questions that decide between them, then covers Saddleback Search's own dimensionality axis on its own.

The three that aren't like the others

Ternary Search doesn't search for a target value at all — it finds the peak of a unimodal sequence, one that strictly rises to a single maximum and then strictly falls. There's no equality check anywhere in it, only a comparison between two probes to see which side is still climbing. Reach for it only when the question is "where does this peak," never "does this value exist" — Ternary Search's own pitfalls measured what happens when it's misapplied to the other six's problem anyway: searching a 64-element sorted array for every one of its own 64 values, a three-way ternary version needs 400 total comparisons against plain binary search's 328 — worse on 43 of the 64 targets, because the extra comparison ternary search pays at every level (checking both m1 and m2) is never paid back by only cutting the range to a third instead of a half.

Golden-Section Search answers the exact same question Ternary Search does — same peak, same unimodal precondition, same O(log n) narrowing — just at a different price per step. Splitting at the golden ratio instead of thirds gives each iteration a property thirds don't have: after discarding a side, one of the two surviving probes is already sitting where the next iteration needed it, so only the other one costs a fresh evaluation. Checked directly against Ternary Search on the identical 31-element arrays both pages use in their own demos: 11–12 evaluations against 19, and 5 narrowing iterations against 8. Reach for it over Ternary Search whenever evaluating a candidate is the expensive part — a real function call, a simulation, a rendered frame — and reach for Ternary Search instead when the array is already sitting in memory, since indexing it is free and the extra floating-point bookkeeping golden-section search needs to track c and d isn't worth it there.

Quickselect doesn't need sorted data at all, and doesn't check for a specific value either — it finds whichever element holds a given rank (the minimum, the median, the k-th smallest) in expected O(n) by reusing quicksort's own partition step, but recursing into only the one side that can possibly hold the answer. Reach for it only when the question is "which element has this rank," not "does this value exist" — the two questions look similar (both narrow down a range) but the "does it exist" question has no notion of rank to exploit, so quickselect's whole speed advantage doesn't transfer.

Binary Search on Answer doesn't search an array at all — it applies the same halving idea to the space of candidate answers to a monotonic yes/no feasibility check (the classic example: the smallest ship capacity that loads every package within a fixed number of days). There's no array of candidates sitting in memory; the range being searched is implicit, bounded only by a floor and a ceiling computed from the problem itself. Reach for it only when the question has that shape — a parameter that only gets easier to satisfy as it grows, checked one value at a time — never for a plain value lookup. The rest of this guide is about the other seven, which do compete directly.

Not even one-dimensional: Saddleback Search

Saddleback Search asks the same question the first seven do — does this value exist — but the data isn't a sequence at all: it's a matrix sorted ascending along every row and every column at once. None of the other eleven entries can even be pointed at that shape without first flattening it, which throws away the exact structure that makes an O(n + m) answer possible in the first place — a full row or column eliminated per comparison, walking in from the top-right corner. Reach for it only when both axes are actually sorted; a matrix that's merely row-sorted (each row internally ordered, but the rows themselves not ordered against each other) breaks it silently — Saddleback Search's own pitfalls measured a 40% wrong-answer rate under exactly that violated assumption, every miss a false "not found" for a value that was really there. On a matrix that's only row-sorted, treat each row as an independent sorted array instead and reach for plain Binary Search on it directly.

Is the data sorted at all?

None of the five entries below this section work on unsorted data — feed Binary Search an unsorted array and it doesn't error, it just silently returns a wrong answer, because bisection's whole mechanism assumes an order that isn't there. Linear Search is the one entry in this family that needs no such assumption: it checks every element in turn, correct on shuffled data exactly as on sorted data, in O(n) worst case — worse than every algorithm below it once the data really is sorted, but the only correct choice when it isn't, or when sorting it first (an O(n log n) cost, paid before the first query even runs) costs more than the linear scans it would save for a single one-off lookup. It also has a real optimization worth knowing about even on its own turf: see its own page for the sentinel trick, verified to exactly halve the naive bounds-checked comparison count whenever the target is present. If the data is sorted — or worth sorting once, for many queries against it — one more question is worth checking before the three below: is it plainly sorted, or sorted and then rotated?

Sorted, but rotated?

The five entries below this section all assume a plain ascending sort. A sorted array that's been rotated at some unknown pivot is neither sorted in that sense nor unsorted — it's still made of two sorted runs, just not one continuous one, and none of the five below handle it correctly: Binary Search's own midpoint comparison silently returns a wrong answer or a false "not found" the moment the array wraps around, much the same failure mode as feeding it unsorted data outright. Search in Rotated Sorted Array keeps the same O(log n) bound by spending one comparison per step figuring out which of the two halves around the midpoint is the genuinely sorted one — there's only ever one rotation break, so it can't be in both — then falling back to plain binary-search logic on whichever half the target's value could actually be in. It's still the same question as the rest of this section — does this value exist, and where — just under a precondition worth checking directly: a sorted array that's been rotated calls for this entry, not the five below it. Its own page also measures the real cost duplicate values add: a genuine wrong answer if the "which half is sorted" comparison isn't handled carefully, and a full O(n) worst case even once it is.

If the data is plainly sorted, not rotated, the three questions below decide among the remaining five.

Three questions, cheapest to check first

Can the data be indexed at all — arr[i] for an arbitrary i — or only read forward one element at a time? A plain array supports the former; a sorted linked list, or any source that only exposes "read the next item," supports only the latter, and that alone settles the choice before anything else matters. If indexing works, is the length known up front? Only relevant once the first answer is "yes, indexable" — an unbounded or streaming source can still be indexed at a given position without anyone knowing where it ends. Is the data verified uniformly distributed by value, at a size where every probe is genuinely expensive? The riskiest question, since nothing detects a wrong answer to it at runtime — get it wrong and the "faster" choice degrades to worse than the safe default.

No indexing at all: Jump Search

Binary search's whole mechanism — jump straight to the midpoint, discard a half, repeat — assumes arr[i] is free for any i. A sorted linked list, or any source that only exposes "read the next item," can't do that at all, and neither can any of the other four entries — even Exponential Search still probes arr[bound] and arr[mid] directly, it just doesn't need to know how big the array is first. Jump Search is the one entry built for genuinely forward-only access: fix a block size, check block boundaries by walking forward a fixed stride at a time until one is found that could hold the target, then scan just that block, in O(√n) comparisons. It never jumps backward or lands on an arbitrary index, only "read forward" and "skip ahead by a fixed count" — exactly what a sorted linked list supports and bisection cannot. The textbook block size √n sits in a flat worst-case-optimal plateau rather than a single sharp minimum (verified by an exhaustive sweep on its own page: 5 through 8 all tie at 11 comparisons on its 36-element demo array, with √36 = 6 comfortably inside that range) — but on a plain array where full indexing is free, binary search's O(log n) still beats it outright (6 comparisons against 11 in the worst case, on that same array), so Jump Search only pays for itself when the access pattern, not the comparison count, forces the choice.

Indexable, but length unknown: Exponential Search

The three entries that need full indexing — binary search, interpolation search, and Fibonacci search — all need to know the array's length before the first probe too, to size the range or the Fibonacci table over the whole array up front. Exponential Search is the one that doesn't: it gallops forward by doubling (1, 2, 4, 8…), probing arr[bound] directly at each step without ever needing to know the array's total size, until it either overshoots the target or runs off the end, then binary-searches the resulting range — all in O(log i) where i is the target's actual index, not the array's length. That's what makes it the standard technique for an unbounded or streaming sorted source, where n isn't known up front at all but a given position can still be queried. The catch, checked on its own page: for a target near the back of a bounded array the doubling phase is overhead paid on top of a binary search that's barely smaller than the one binary search alone would have run — 12 probes against binary search's 7 on that page's own 64-element array, the exact opposite of the 4-against-6 win a front-loaded target gets. Reach for it only when the length is genuinely unavailable, or there's a real reason to expect the target sits near the front — not as a general-purpose faster binary search on data whose length is already known.

Random access available: is the distribution actually uniform?

With a plain array in hand, Binary Search is the safe default — O(log n) guaranteed regardless of what the values look like, no assumptions beyond "sorted." Interpolation Search trades that guarantee for speed: instead of always probing the midpoint, it uses the values at the range's two ends to guess where the target should sit, converging in a doubly-logarithmic O(log log n) average probes when the data really is close to uniform. The trade is real and undetectable in advance: on its own page's deliberately skewed example — eleven consecutive integers followed by one outlier a million higher — it takes 11 probes (effectively a full linear scan) to binary search's 3 on the identical array and target, and interpolation search never notices anything went wrong; it just quietly does more work. It's worth reaching for only when the data is known, not just hoped, to be roughly uniform, and each probe's own cost is high enough for the gap between log log n and log n to matter — a disk seek or a network round trip, not a plain in-memory comparison. That's a question about probe cost, not array size: measured on its own page, interpolation search is already using under half as many real probes as binary search by n=100, far short of what "large" usually implies — the array doesn't need to be huge for the relative win to show up, only for the saved probes to be worth much when they're nearly free.

If the distribution isn't known to be uniform, stick with Binary Search — which leaves one remaining question for the cases where it still applies.

Is division itself expensive?

Fibonacci Search solves the identical problem as Binary Search — same O(log n) asymptotic class, same sorted-array precondition, same need to know the length up front — but never divides or multiplies, splitting each range at the golden-ratio point using Fibonacci numbers and only addition and subtraction. That was the actual point historically: on hardware where division was slow or unavailable, an addition-only search was worth an uneven split. The uneven split has a real cost, checked on its own page's presets: 2 probes against binary search's 4 for an early target, but 6 against 5 for a target on the very last element of the same 20-element array — the golden-ratio split front-loads its advantage the same way Exponential Search's doubling does. On any modern general-purpose CPU, where division is no longer meaningfully slower than addition, there's no reason to pay that variance — Binary Search wins by default. Reach for Fibonacci Search only in the historical or embedded contexts its own division-free property actually exists for.

Side by side

EntryAccess neededTimeNeeds length up front?Reach for it when
Linear Search forward only (works on random access too) O(n) not required data isn't sorted, or not worth sorting for a single lookup
Binary Search random O(log n) yes the general default — plain sorted array, no special assumptions
Search in Rotated Sorted Array random O(log n) avg, O(n) worst (many duplicates) yes a sorted array that's been rotated at an unknown pivot
Interpolation Search random O(log log n) avg (uniform), O(n) worst yes verified-uniform numeric data, large enough that every probe is expensive
Exponential Search indexed (arr[i] for any i) O(log i), i = target's index no unbounded or streaming sorted source, length genuinely unknown
Jump Search forward, fixed stride only O(√n) not required no indexing available at all — a sorted linked list
Fibonacci Search random O(log n) yes division is genuinely expensive on the target hardware
Ternary Search random O(log n), larger constant yes a different question — the peak of a unimodal sequence, not a value lookup
Golden-Section Search random O(log n), fewer evaluations than Ternary Search yes the same different question as Ternary Search — peak of a unimodal sequence — when each evaluation is expensive
Quickselect random O(n) avg, O(n²) worst (O(n) worst with median-of-medians) not required a different question — which element holds a given rank, not a value lookup
Binary Search on Answer none — searches a numeric range, not an array O(n log(range)) not applicable a different question — the smallest/largest value satisfying a monotonic feasibility check
Saddleback Search random, over a matrix, not an array O(n + m) yes (matrix dimensions) a different shape entirely — a matrix sorted along both rows and columns

Race them yourself

Every measured number above comes from one specific example on that algorithm's own page. This runs the exact reference implementation from each of the seven entries above that actually compete on the same question — does this value exist, and where — unmodified, in your own browser, against a freshly generated array: Linear Search, Binary Search, Search in Rotated Sorted Array, Interpolation Search, Exponential Search, Jump Search, and Fibonacci Search. (Ternary Search, Golden-Section Search, Quickselect, Binary Search on Answer, and Saddleback Search are left out on purpose — each answers a different question, per the sections above, so racing them against these seven would compare apples to a different fruit entirely.) These algorithms are all too fast for performance.now() to time meaningfully in a single call — JIT warmup and GC noise would swamp the actual signal the way they don't for the comparison-sort race's much heavier O(n log n) work. So instead of timing, this counts array reads: the array is wrapped in a Proxy that increments a counter every time any of the seven touches an index, an exact number rather than an estimate. It isn't the same thing as wall-clock speed, though — Interpolation Search's per-step arithmetic is heavier than Binary Search's plain midpoint, so an equal read count doesn't mean equal time. Measured directly, outside the browser: timing both pages' own verbatim reference implementations on the same uniform arrays this race generates, with loop iterations counted alongside the wall clock to get a cost per step rather than per call — Interpolation Search's step costs roughly 1.5× Binary Search's at n=1,000-10,000, widening to roughly 2.3×-2.5× at n=100,000-1,000,000 (Node v20.20.2), from the subtraction, multiplication, and division the probe formula runs versus one subtraction and a shift-like halving. It still finishes faster overall at these sizes because it needs so many fewer steps in the first place — the per-step tax doesn't erase the doubly-logarithmic win on data this well-behaved, it just means the step-count race above isn't the whole story.

Press "Run race" to search all seven reference implementations against the same array.

Switch data to skewed and watch Interpolation Search specifically: on uniform data at 100,000 elements averaged over 500 queries, it needs about as many reads as Binary Search does — one run measured 27 against Binary Search's 30 — the doubly-logarithmic edge over O(log n) is real but small at sizes like this, not the dramatic win the asymptotic classes alone suggest. Introduce a single outlier a hundred times the array's own range — generalizing Interpolation Search's own pitfalls example, eleven consecutive integers plus one outlier a million higher — and that same average explodes past 13,000 reads at the same size, while Binary Search's own average doesn't move at all, since it never looks at the values themselves, only their order. The size makes it worse, not better: the average climbed from roughly 2,400 reads at 1,000 elements to roughly 6,600 at 10,000 to roughly 13,000 at 100,000, measured across repeated runs — the exact opposite of what a reader hoping "it'll average out at scale" would want to see.

Two smaller, consistent patterns worth switching target to see: Search in Rotated Sorted Array pays a steady ~2.5× over plain Binary Search's own average at every size tested (1,000, 10,000, and 100,000 elements) — the real, measured cost of the extra which-half-is-sorted branch every iteration pays for tolerating rotation. Jump Search's average grows with √n (47 at 1,000, 131 at 10,000, 471 at 100,000 — always a small multiple of √n, though not a perfectly constant one), visibly outgrowing every O(log n) entry as the array grows, exactly as its own complexity section says it should. Fibonacci Search is the one surprise: its own page shows it losing to Binary Search on small, specific examples when the target sits near the end, but averaged over many queries here it comes in with fewer reads than Binary Search at every size tested, not more — a reminder that a single worked example and a broad average can point in different directions even for algorithms in the same complexity class.

This is the site's fifth guide, following the same pattern as the first four: a cross-cutting page comparing existing entries instead of adding a new algorithm, for a family that had grown large enough (six entries when this guide was first written) that "which one do I use" is a real question a reader would have. Grown to seven with Linear Search, then eight with Quickselect, then nine with Search in Rotated Sorted Array, then ten with Binary Search on Answer, then eleven with Saddleback Search — the first to change the data's shape rather than just the question asked about it — then twelve with Golden-Section Search, a second entry answering Ternary Search's own peak-finding question instead of a new one. See the journal for each addition's own session notes.