16.06Beginner / Intermediate5 topics24 min5 interactive animations

Other searches

Binary search is not the only way to search sorted data. These alternatives trade probes for different strengths: cheap backward steps, unknown sizes, uniform data, addition-only arithmetic, or finding the top of a hill.

Learning goals

Trace jump, exponential, interpolation and Fibonacci search
Compare their probe counts and the data each one suits
Use ternary search to find the maximum of a unimodal sequence

Prerequisites

Binary searchSquare roots and logarithms

16.06.1

Jump search

Jump ahead in blocks of √n, checking only the last element of each block. Once a block ends with a value >= target, scan that one block linearly.

The worst case is √n jumps plus √n scans, so O(√n). This is slower than binary search, but it moves backward at most once, which helps when stepping back is expensive, such as on tape or with some linked structures.

Best

O(1)

Worst

O(√n)

Space

O(1)

Jump search

Interactive · edit the input

int[] arr · length 13

0123456789101112

Being comparedNot a matchAlready checkedDiscardedMatch / answer

Setup

step = floor(√13) = 3. Jump block by block, then scan one block.

Step 1 / 11

Java

1public static int jumpSearch(int[] arr, int target) {
2    int n = arr.length;
3    int step = (int) Math.sqrt(n);
4    int prev = 0, curr = step;
5    while (curr < n && arr[curr - 1] < target) {
6        prev = curr;
7        curr += step;
8    }
9    for (int i = prev; i < Math.min(curr, n); i++) {
10        if (arr[i] == target) return i;
11    }
12    return -1;
13}

Live state

0 comparisons

target

step

No condition evaluated on this step

Execution trace (dry run table)Show 11 steps

Step	Line	State	What happens
1	L3	target=30 n=13 step=3	step = floor(√13) = 3. Jump block by block, then scan one block.
2	L4	target=30 step=3 prev=0 curr=3	First block is [0, 2].
3	L5	target=30 step=3 prev=0 curr=3 arr[curr-1]=7	The block ends with 7, still smaller than 30. Skip the whole block.
4	L7	target=30 step=3 prev=3 curr=6	Jump: prev = 3, curr = 6.
5	L5	target=30 step=3 prev=3 curr=6 arr[curr-1]=17	The block ends with 17, still smaller than 30. Skip the whole block.
6	L7	target=30 step=3 prev=6 curr=9	Jump: prev = 6, curr = 9.
7	L5	target=30 step=3 prev=6 curr=9 arr[curr-1]=30	The block ends with 30 >= 30. If the target exists, it is in this block.
8	L10	target=30 prev=6 i=6 arr[i]=21	Linear scan inside the block.
9	L10	target=30 prev=6 i=7 arr[i]=26	Linear scan inside the block.
10	L10	target=30 prev=6 i=8 arr[i]=30	Match inside the block.
11	L10	target=30 return=8	return 8 after 6 comparisons. Jump search is O(√n).

16.06.2

Exponential search

Check indices 1, 2, 4, 8, … until the value there is >= target or you run off the end, then binary search between the last two bounds.

If the target is at index i, this costs O(log i) rather than O(log n), which is good when targets tend to sit near the front. It also works on unbounded or unknown-length streams.

Best

O(1)

Worst

O(log i)

Space

O(1)

Exponential search

Interactive · edit the input

int[] arr · length 13

0123456789101112

Being comparedNot a matchDiscardedMatch / answer

Compare

Check index 0 separately, then start doubling from 1.

Step 1 / 17

Java

1public static int exponentialSearch(int[] arr, int target) {
2    if (arr[0] == target) return 0;
3    int bound = 1;
4    while (bound < arr.length && arr[bound] < target) {
5        bound *= 2;
6    }
7    int lo = bound / 2, hi = Math.min(bound, arr.length - 1);
8    while (lo <= hi) {
9        int mid = lo + (hi - lo) / 2;
10        if (arr[mid] == target) return mid;
11        if (arr[mid] < target) lo = mid + 1;
12        else hi = mid - 1;
13    }
14    return -1;
15}

Live state

1 probes

target

arr[0]

arr[0] (1) == target (35)false

Execution trace (dry run table)Show 17 steps

Step	Line	State	What happens
1	L2	target=35 arr[0]=1	Check index 0 separately, then start doubling from 1.
2	L4	target=35 bound=1 arr[bound]=4	4 < 35, so double the bound.
3	L5	target=35 bound=2	bound = 2.
4	L4	target=35 bound=2 arr[bound]=7	7 < 35, so double the bound.
5	L5	target=35 bound=4	bound = 4.
6	L4	target=35 bound=4 arr[bound]=13	13 < 35, so double the bound.
7	L5	target=35 bound=8	bound = 8.
8	L4	target=35 bound=8 arr[bound]=30	30 < 35, so double the bound.
9	L5	target=35 bound=16	bound = 16.
10	L4	target=35 bound=16	bound ran past the end, so the range is capped at the last index.
11	L7	target=35 lo=8 hi=12	Binary search only inside [8, 12]. Cost is O(log i) where i is the target's position.
12	L10	target=35 lo=8 hi=12 mid=10 arr[mid]=41	mid = 10.
13	L12	target=35 lo=8 hi=9	hi = 9.
14	L10	target=35 lo=8 hi=9 mid=8 arr[mid]=30	mid = 8.
15	L11	target=35 lo=9 hi=9	lo = 9.
16	L10	target=35 lo=9 hi=9 mid=9 arr[mid]=35	mid = 9.
17	L10	target=35 return=9	return 9 after 8 probes.

16.06.3

Interpolation search

Instead of probing the middle, estimate where the target should be by linear interpolation between arr[lo] and arr[hi], much as you open a phone book near the back for a name starting with W.

On uniformly distributed keys this averages O(log log n) probes. On skewed data the estimates can be poor and it degrades to O(n). Compare the “Uniform data” and “Skewed data” presets.

Best

O(1)

Average

O(log log n)

Worst

O(n)

Space

O(1)

Interpolation search

Interactive · edit the input

int[] arr · length 10

100

0123456789

Being comparedNot a matchDiscardedMatch / answer

Setup

Instead of the middle, guess where the target should be if values were evenly spread.

Step 1 / 5

Java

1public static int interpolationSearch(int[] arr, int target) {
2    int lo = 0, hi = arr.length - 1;
3    while (lo <= hi && target >= arr[lo] && target <= arr[hi]) {
4        if (arr[hi] == arr[lo]) return arr[lo] == target ? lo : -1;
5        int pos = lo + (int) ((long) (target - arr[lo]) * (hi - lo) / (arr[hi] - arr[lo]));
6        if (arr[pos] == target) return pos;
7        if (arr[pos] < target) lo = pos + 1;
8        else hi = pos - 1;
9    }
10    return -1;
11}

Live state

0 probes

target

No condition evaluated on this step

Execution trace (dry run table)Show 5 steps

Step	Line	State	What happens
1	L2	target=70 lo=0 hi=9	Instead of the middle, guess where the target should be if values were evenly spread.
2	L3	target=70 lo=0 hi=9	The target is within the value range of the window.
3	L5	target=70 lo=0 hi=9 pos=6	pos = 0 + (70 - 10) × (9 - 0) / (100 - 10) = 6.
4	L6	target=70 lo=0 hi=9 pos=6 arr[pos]=70	Direct hit after 1 probe.
5	L6	target=70 return=6	return 6. On uniform data this averages O(log log n) probes.

16.06.4

Fibonacci search

Fibonacci search splits the window at Fibonacci-number offsets instead of halves, so it needs only addition and subtraction to compute probe positions. Historically that mattered on machines where division was slow.

It probes O(log n) times and examines positions that are closer together, which can help locality on very large or slow storage.

Best

O(1)

Worst

O(log n)

Space

O(1)

Fibonacci search

Interactive · edit the input

int[] arr · length 11

100

012345678910

Being comparedNot a matchDiscardedMatch / answer

Setup

The smallest Fibonacci number >= 11 is 13. The window will shrink through Fibonacci sizes using only addition and subtraction.

Step 1 / 13

Java

1public static int fibonacciSearch(int[] arr, int target) {
2    int n = arr.length;
3    int fib2 = 0, fib1 = 1, fib = fib2 + fib1;
4    while (fib < n) {
5        fib2 = fib1;
6        fib1 = fib;
7        fib = fib2 + fib1;
8    }
9    int offset = -1;
10    while (fib > 1) {
11        int i = Math.min(offset + fib2, n - 1);
12        if (arr[i] < target) {
13            fib = fib1; fib1 = fib2; fib2 = fib - fib1;
14            offset = i;
15        } else if (arr[i] > target) {
16            fib = fib2; fib1 = fib1 - fib2; fib2 = fib - fib1;
17        } else {
18            return i;
19        }
20    }
21    if (fib1 != 0 && offset + 1 < n && arr[offset + 1] == target) return offset + 1;
22    return -1;
23}

Live state

0 probes

target

fib2

fib1

fib

No condition evaluated on this step

Execution trace (dry run table)Show 13 steps

Step	Line	State	What happens
1	L7	target=85 n=11 fib2=5 fib1=8 fib=13	The smallest Fibonacci number >= 11 is 13. The window will shrink through Fibonacci sizes using only addition and subtraction.
2	L9	target=85 fib2=5 fib1=8 fib=13 offset=-1	offset marks the last index known to be smaller than the target.
3	L11	target=85 fib2=5 fib1=8 fib=13 offset=-1 i=4	Probe i = min(-1 + 5, 10) = 4.
4	L12	target=85 fib2=5 fib1=8 fib=13 offset=-1 i=4 arr[i]=45	Too small. Drop everything up to i and step the Fibonacci numbers down by one.
5	L14	target=85 fib2=3 fib1=5 fib=8 offset=4	offset = 4.
6	L11	target=85 fib2=3 fib1=5 fib=8 offset=4 i=7	Probe i = min(4 + 3, 10) = 7.
7	L12	target=85 fib2=3 fib1=5 fib=8 offset=4 i=7 arr[i]=82	Too small. Drop everything up to i and step the Fibonacci numbers down by one.
8	L14	target=85 fib2=2 fib1=3 fib=5 offset=7	offset = 7.
9	L11	target=85 fib2=2 fib1=3 fib=5 offset=7 i=9	Probe i = min(7 + 2, 10) = 9.
10	L15	target=85 fib2=2 fib1=3 fib=5 offset=7 i=9 arr[i]=90	Too large. Keep the left part and step the Fibonacci numbers down by two.
11	L16	target=85 fib2=1 fib1=1 fib=2 offset=7	fib = 2.
12	L11	target=85 fib2=1 fib1=1 fib=2 offset=7 i=8	Probe i = min(7 + 1, 10) = 8.
13	L18	target=85 return=8	return 8 after 4 probes.

16.06.5

Ternary search for unimodal functions

A unimodal sequence strictly rises and then strictly falls. Compare two interior points m1 < m2. If f(m1) < f(m2), the maximum cannot lie in [lo, m1]. Otherwise it cannot lie in [m2, hi]. Each step removes about a third of the window.

Ternary search is mainly used on functions (including real-valued ones) to find a maximum or minimum. For searching a sorted array, binary search makes fewer comparisons.

Java

1// real-valued version: maximise a unimodal f on [lo, hi]
2for (int iter = 0; iter < 100; iter++) {
3    double m1 = lo + (hi - lo) / 3, m2 = hi - (hi - lo) / 3;
4    if (f(m1) < f(m2)) lo = m1;
5    else hi = m2;
6}
7return (lo + hi) / 2;

Worst

O(log n)

Space

O(1)

Ternary search (maximum of a unimodal array)

Interactive · edit the input

int[] arr · length 9

012345678

Being comparedNot a matchDiscardedMatch / answer

Setup

Comparing two inner points tells us which third cannot contain the maximum.

Step 1 / 14

Java

1public static int ternaryMax(int[] arr) {
2    int lo = 0, hi = arr.length - 1;
3    while (hi - lo > 2) {
4        int m1 = lo + (hi - lo) / 3;
5        int m2 = hi - (hi - lo) / 3;
6        if (arr[m1] < arr[m2]) {
7            lo = m1 + 1;      // max is not in [lo, m1]
8        } else {
9            hi = m2 - 1;      // max is not in [m2, hi]
10        }
11    }
12    int best = lo;
13    for (int i = lo + 1; i <= hi; i++) {
14        if (arr[i] > arr[best]) best = i;
15    }
16    return best;
17}

Live state

0 comparisons

No condition evaluated on this step

Execution trace (dry run table)Show 14 steps

Step	Line	State	What happens
1	L2	lo=0 hi=8	Comparing two inner points tells us which third cannot contain the maximum.
2	L3	lo=0 hi=8	Window still has more than three cells.
3	L6	lo=0 hi=8 m1=2 m2=6 arr[m1]=9 arr[m2]=12	m1 is lower, so m1 is on the rising slope. Drop [lo, m1].
4	L7	lo=3 hi=8	lo = 3.
5	L3	lo=3 hi=8	Window still has more than three cells.
6	L6	lo=3 hi=8 m1=4 m2=7 arr[m1]=22 arr[m2]=7	m2 is not higher, so m2 is on the falling slope. Drop [m2, hi].
7	L9	lo=3 hi=6	hi = 6.
8	L3	lo=3 hi=6	Window still has more than three cells.
9	L6	lo=3 hi=6 m1=4 m2=5 arr[m1]=22 arr[m2]=18	m2 is not higher, so m2 is on the falling slope. Drop [m2, hi].
10	L9	lo=3 hi=4	hi = 4.
11	L3	lo=3 hi=4	Three or fewer cells left. Finish with a short scan.
12	L12	lo=3 hi=4 best=3	Start with best = 3.
13	L14	lo=3 hi=4 best=3 i=4	New best = 4.
14	L16	return=4	return 4: the maximum is 22, found with 4 comparisons.

Practice ladder

Now try it yourself

Easy

Implement jump search and count comparisons for n = 100
Find an element in a sorted array of unknown size

Medium

Peak of a bitonic array with ternary search
Compare probe counts of binary vs interpolation search on random uniform data

Advanced

Minimise a convex cost function of a real parameter
Fibonacci search on a disk-backed array and measure seeks

Key takeaways

Jump search is O(√n); exponential search is O(log i); interpolation search is O(log log n) on uniform data.
Fibonacci search avoids division; ternary search finds the extremum of a unimodal function.
For general sorted arrays in memory, plain binary search is still the default.