Skip to content
Tutorials Center
My learning

Topics

Lesson 76 of 225 ยท Searching

Jump, Exponential, Interpolation, Ternary and Other Searches

Learn searches beyond binary search in Python: jump, exponential, interpolation, ternary, meta binary, Fibonacci and best-first search, with traces and step counts.

Binary search is the default way to search sorted data, and for most problems it is all you need. But it is not the only idea. Other searches make different trade-offs: some move only forward, some work when you do not know how long the data is, some guess where a value should be, and one does not look for a value at all but for the peak of a curve.

In this lesson you will build seven of them from scratch: jump search, exponential search, interpolation search, ternary search, meta binary search, Fibonacci search and best-first search. Each one comes with a picture, a trace, a step counter and an honest answer to "when would I really use this?". Most of them require sorted input, except the last one, which requires a shape instead.

Jump search sits between linear search and binary search. Instead of checking every item, you jump ahead in blocks of size m until you pass the target, then walk through the one block that can contain it.

TEXT
sorted: [ 2  5  8 12 | 16 23 38 56 | 72 91 ...]      target = 23, block size 4
          jump to index 3 (12)  -> 12 < 23, keep jumping
          jump to index 7 (56)  -> 56 >= 23, stop
          scan index 4..7 left to right: 16, 23 -> found

The best block size is about the square root of n. With a block of size m, you make at most n / m jumps and then at most m - 1 single steps, and n / m + m is smallest when m = sqrt(n). That gives O(sqrt(n)) time and O(1) space.

Python Jump search with a step counter

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Look at the last line of output: on a million sorted numbers, finding the very last one took 2,000 comparisons (1,000 jumps plus 1,000 steps inside the final block). That is far fewer than the million of a linear search, but far more than the 20 of binary search.

Jump search is rarely the best choice in Python, because binary search needs only O(log n) steps. Its niche is data where going backwards is expensive or impossible: binary search jumps back and forth, while jump search only ever moves forward and goes back at most one block. Think of tape-like storage or a linked structure with skip pointers. Interview questions also love it as a comparison point.

What if you do not know how big the sorted data is? Maybe it is a stream, an endless sequence of values, or a function you can only probe. You cannot run binary search without an upper bound, so exponential search finds one by doubling.

  1. Check index 1, 2, 4, 8, 16 ... until the value there is at least the target (or you run past the end).
  2. Run binary search between the previous power of two and the current one.
TEXT
target = 37, sorted list
index:   1    2    4    8    16   32   64
value:   3    5    9   14    21   30   44    <- 44 >= 37: stop doubling
                                  \_____/
                         binary search in indexes 32..64

Doubling takes about log2(i) steps to reach the target's position i, and the binary search over a range of size about i takes log2(i) more. The total is O(log i), where i is the target's position, not the size of the data. So it is as good as binary search on a fixed list, and much better when the target sits near the front of a huge one.

Python Exponential search: doubling then binary search

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Finding 10, which sits at index 5, took 8 comparisons, however large the list is. Finding the last of a million items took 40: about twice what plain binary search needs, because you pay for the doubling and then for the search. That is the price of not knowing the length.

A famous use is searching a sorted sequence that is unbounded: you keep doubling until you find a bound, and you never need to know the length. The same doubling trick shows up when you search for the smallest x that satisfies a condition and have no idea how large x can be (see binary search on the answer).

When you look up a name in a phone book, you do not open it in the middle. If the name starts with "Z", you open near the back. Interpolation search does the same: instead of always checking the middle, it estimates the position from the values.

If the values are spread roughly evenly between items[lo] and items[hi], the target should sit at this fraction of the way along:

TEXT
pos = lo + (target - items[lo]) * (hi - lo) / (items[hi] - items[lo])
TEXT
items: 10 ............................................ 1000
target 900 -> fraction (900-10)/(1000-10) = 0.9 -> start looking at 90% of the way

On uniformly distributed data, it needs only about O(log log n) steps on average. For a million items that is roughly 4 or 5 probes instead of 20. On skewed data, such as values that grow exponentially, the estimate is terrible and it can degrade to O(n).

Python Interpolation search versus binary search

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

On evenly spaced data, interpolation search found the target with a single probe, where binary search needed 20. On the skewed list of powers of two, it was a disaster: 41 probes against 4 for binary search.

Interpolation search does arithmetic on the values, so it only works on numbers (or things you can map to numbers). It also divides by items[hi] - items[lo], which is zero when many values are equal. Always guard that case, as the code above does.

The three searches above look for a value in sorted data. Ternary search looks for the maximum (or minimum) of a unimodal function: one that rises to a single peak and then falls (or the reverse), with no other bumps.

TEXT
f(x)
  |        .  *  .
  |     .          .
  |   .              .
  | .                   .
  +-------------------------- x
   lo   m1       m2       hi

Pick two points, m1 and m2, that split the range into three parts, and compare f(m1) with f(m2):

  • If f(m1) < f(m2), the peak cannot be left of m1, so set lo = m1.
  • Otherwise the peak cannot be right of m2, so set hi = m2.

Each round discards a third of the range, so the number of rounds is about log base 1.5 of the range, which is O(log n). It is slightly more comparisons per halving than binary search, and for integers a smarter option is binary search on the slope (compare f(mid) with f(mid + 1)), as in the peak element problem. Ternary search shines for real-valued functions, where you just repeat until the interval is tiny.

Python Ternary search for the peak of a curve

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The float version converges on 4.2, and the integer version finds that a price of 25 maximises profit (25 times 50 = 1,250) using 21 evaluations of f in total.

Ternary search is only correct when the function is strictly unimodal. Flat stretches (plateaus) can make f(m1) == f(m2) while the peak is on neither side, and the search can walk the wrong way. If your data may have plateaus, use a different approach.

Meta binary search (also called one-sided binary search) is binary search without lo, hi and mid. Instead you build the answer's index one bit at a time, from the highest bit down. The index of any item in a list of n items fits in (n - 1).bit_length() bits, so you need only that many probes.

For each bit, from high to low, ask: "if I switch this bit on, does the candidate position still hold a value that is <= the target?" If yes, keep the bit. When all bits are decided, pos is the last index whose value is at most the target, and one final comparison tells you whether it is an exact hit.

TEXT
n = 10 -> 4 bits.   target = 23 in [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
bit 8: pos 8 -> 72 <= 23? no.     pos stays 0
bit 4: pos 4 -> 16 <= 23? yes.    pos = 4
bit 2: pos 6 -> 38 <= 23? no.     pos stays 4
bit 1: pos 5 -> 23 <= 23? yes.    pos = 5     -> items[5] == 23, found

It makes the same number of comparisons as ordinary binary search, but the loop body has no division and no lo/hi bookkeeping, which makes it popular for tight loops and for languages where bit operations are cheap.

Python Meta binary search: building the index bit by bit

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Because the loop keeps the last position that is <= target, a list with duplicates returns the last copy of the value.

Fibonacci search is another way to split a sorted list, using Fibonacci numbers (1, 1, 2, 3, 5, 8, 13, ...) instead of halves. It finds the smallest Fibonacci number F(k) that is at least n, then probes at the offset F(k-2). Each probe throws away either the front F(k-2) items or the back F(k-1) items, so the range always shrinks to the previous or the second-previous Fibonacci number. The cost is O(log n), with a slightly larger constant than binary search.

Its selling point is that the probes use only addition and subtraction (no division by two), and that probe positions stay close to the previous ones when you move forward. That helped on old hardware and on storage where nearby reads are cheaper (tapes and spinning disks). Today it is mostly a classic to know, not a tool you reach for.

Python Fibonacci search

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Every search so far looks through a sorted sequence. Best-first search is different: it explores a graph or grid and always expands the node that looks closest to the goal, according to a heuristic (a cheap estimate). A priority queue keeps the most promising node on top.

Compare it with breadth-first search, which expands nodes in the order it found them, with no idea where the goal is. Best-first search uses the estimate to head straight for the goal, so it usually expands far fewer cells. The price: plain (greedy) best-first search trusts the estimate blindly, so the path it finds can be longer than the shortest one. Dijkstra's algorithm orders by distance travelled, A* orders by distance travelled plus the estimate, and greedy best-first uses the estimate alone.

The next example finds a way through a small maze (S start, G goal, # wall) with Manhattan distance as the estimate, and compares it with BFS.

Python Greedy best-first search versus BFS on a maze

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Best-first expanded 28 cells against BFS's 46, but its route is 27 steps long while BFS finds the shortest one, 21 steps. The estimate lured it along a long detour. If you need the shortest path and a guiding estimate, use A*, which adds the distance already travelled to the estimate.

Which search should you use?

Search Needs Time When it helps
Linear nothing O(n) tiny or unsorted data
Binary sorted, random access O(log n) the default
Jump sorted, forward-friendly O(sqrt(n)) going backwards is costly
Exponential sorted, unknown size O(log i) unbounded data, target near the front
Interpolation sorted, uniform numbers O(log log n) average, O(n) worst big evenly spread numeric tables
Ternary unimodal function O(log n) peak of a real-valued function
Meta binary sorted, random access O(log n) binary search without division or lo/hi
Fibonacci sorted, random access O(log n) splitting with only addition and subtraction
Best-first graph plus a heuristic depends on the graph reaching a goal fast when the path need not be shortest

In everyday Python, use in for small lists, a set or dict for membership, and the bisect module for sorted lists. Reach for the searches in this lesson when the problem statement gives you the hint: unknown length, uniform numbers, a curve with one peak.

Common mistakes

  • Using jump or interpolation search on unsorted data. The results are silently wrong.
  • Forgetting to cap indexes with min(..., n - 1) when a block or a doubling step goes past the end.
  • Dividing by zero in interpolation search when items[lo] == items[hi].
  • Using ternary search on a function with plateaus or several peaks.
  • Running ternary search on floats with an exit test like hi - lo > 0 that never becomes false; use a fixed number of rounds or a tolerance.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What block size minimises the total work of jump search on n sorted items?

    With block size m you make about n / m jumps plus up to m - 1 steps inside a block. The sum n / m + m is smallest at m = sqrt(n), giving O(sqrt(n)).
  2. 2. Which search finds a value in a sorted list whose length you do not know?

    Exponential search doubles an index until it passes the target, which gives it an upper bound, then runs binary search inside that range. It never needs the length.
  3. 3. On which data does interpolation search perform worst?

    Interpolation search assumes values are spread evenly. When they are heavily skewed the position estimate is poor, and the search can degrade to O(n).
  4. 4. What does ternary search look for?

    Ternary search discards a third of the range each round by comparing f at two inner points. It only works when the function rises to one peak and then falls (or the reverse).
  5. 5. Why is exponential search O(log i), where i is the target's position?

    Reaching a bound above i takes about log2(i) doublings. The range between the last two bounds is about i wide, so the binary search needs about log2(i) more comparisons.

Summary

  • Jump search moves forward in blocks of about sqrt(n) and scans one block: O(sqrt(n)) time, O(1) space, useful when moving backwards is costly.
  • Exponential search doubles an index to find an upper bound, then runs binary search: O(log i), perfect for unbounded sorted data.
  • Interpolation search guesses the position from the values: O(log log n) on uniform numbers, but O(n) on skewed data.
  • Ternary search finds the peak of a unimodal function by discarding a third of the range each round.
  • Meta binary search builds the index bit by bit, Fibonacci search splits by Fibonacci numbers; both are O(log n) and need sorted input.
  • Best-first search expands the node with the best heuristic estimate first: fast, but not guaranteed to give the shortest path.
  • All value searches here need sorted input; ternary search needs a single peak and best-first search needs a graph.
  • Binary search remains the right default; the others are for specific shapes of problem.

Next: Sorting Basics