This site has eleven Searching entries now — Binary Search, Interpolation Search, Exponential Search, Jump Search, Fibonacci Search, Linear Search, Search in Rotated Sorted Array, Ternary Search, Quickselect, Binary Search on Answer, and Saddleback Search — each built, verified, and explained on its own page. Ten of the eleven search a one-dimensional array (or, for Binary Search on Answer, an implicit range of candidate answers). Of those ten, 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. Three more, Ternary Search, Quickselect, and Binary Search on Answer, each answer a different question altogether. The eleventh, 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 ten can even represent. This guide sorts the ten one-dimensional entries by the actual questions that decide between them, then covers Saddleback Search's own dimensionality axis on its own.
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.
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.
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 ten 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.
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?
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.
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.
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.
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.
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 the array is large enough that the gap between log log
n and log n matters — the sizes where every probe is a disk seek or a network
round trip, not a small in-memory array where the difference is a couple of comparisons either way.
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.
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.
| Entry | Access needed | Time | Needs 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 |
| 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 |
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. See the journal for each addition's own session notes.