Comparisons
Still possible
Binary search would need

  • Target
  • Still possible
  • Compared
  • Ruled out
  • Found

More about exponential search

Exponential search

Exponential search finds a value in a sorted list in two phases. First it looks at places 1, 2, 4, 8, 16 and so on, doubling each time, until the value there is not smaller than the target. Then it binary-searches the stretch between the last two places. Choose the value to look for and see why targets near the start are found in just a few comparisons. Press Play to watch the search, or Step and Back to go one step at a time. Drag the step slider to jump anywhere. The dashed line marks the value you search for, and the shaded part is where it can still be. Exponential search needs a sorted list, so an unsorted list is sorted first. Choose the value, how many bars, or type your own numbers. With the board selected, the arrow keys step, the space bar plays and pauses, and Home and End jump to the start and the end.

How it works

  1. Choose the value to search for, and how many bars. Or type your own numbers: exponential search sorts them first.
  2. Press Play, or use Step and Back to move one step at a time. Drag the step slider to jump anywhere in the search.
  3. Search for a value near the start and one near the end, and compare the count with Binary search would need.

How exponential search works

Look at the value at place 1. If it is smaller than the target, look at place 2, then 4, 8, 16, doubling each time. As soon as a value is not smaller, stop: the target can only lie after the previous place looked at and before this one. Binary-search that stretch. If the doubling runs past the end of the list, binary-search from the last place looked at to the end.

Fast near the start, and no length needed

To reach a target at place i, the doubling takes about log₂ i looks, and the stretch it finds holds fewer than i values, so the binary search takes about log₂ i more. That is about 2 log₂ i in all, which depends on where the target is, not on how long the list is. Targets near the start are found faster than with plain binary search; targets near the end cost up to about twice as much. Because it never needs the length of the list, it also works on lists that are too long to measure or have no known end.

Frequently asked questions

How does exponential search work?

On a sorted list it checks places 1, 2, 4, 8 and so on until the value there is not smaller than the target. Then the target can only lie between the last two places checked, and a binary search of that stretch finds it.

Is exponential search faster than binary search?

When the target is near the start of the list, yes: it takes about 2 log₂ i comparisons for a target at place i, whatever the length of the list. When the target is near the end, plain binary search is faster, by up to about a factor of two.

What is it used for?

Searching lists whose length is unknown or unbounded, such as a stream or an infinite sequence, and merging sorted runs, where the next match is usually close by. Timsort's galloping mode uses the same doubling idea.

Why is it called exponential?

Because the places it checks grow exponentially: 1, 2, 4, 8, 16, each twice the one before. It is also called doubling search or galloping search.

Are my numbers sent anywhere?

No. The search runs in your browser, and your last settings stay in this browser's local storage.

Ready to try it?

Open PictorX in your browser — no install, no credit card required to start.

Go to Editor