1248163264128256512
ALGO.ANIMATED · SEARCHING

Exponential Search Explained with Animations

Gallop across sorted arrays with exponential jumps (1, 2, 4, 8...), then binary search the found range. Perfect for unbounded arrays. O(log n) — fast and elegant.

// WHAT YOU'LL LEARN

🐎Galloping Phase
⚡O(log n) Complexity
∞Unbounded Arrays
🔍Binary Search Phase
⚖️Exponential vs Binary
📋Flowchart & Pseudocode
Intermediate·12 min·Algorithms / Searching
Reviewed by CodeTikki Academic Team

Prerequisites: Binary search · Sorted arrays · Logarithms

// DEFINITION

What is
exponential search?

Exponential search (also called galloping search or doubling search) finds a target in a sorted array by first jumping with exponentially increasing steps (1, 2, 4, 8, 16...) until it overshoots the target, then binary searches the small range where the target must be.

It works on sorted arrays and has O(log n) time complexity. Its superpower: it works even when you don't know the array size — perfect for unbounded or infinite arrays.

PHASE 1 — GALLOP 🐎
2
5
8
12
16
23
38
56
72
91
Check arr[0] = 2 → ≤ 72, continue
Check arr[1] = 5 → ≤ 72, double to 2
Check arr[2] = 8 → ≤ 72, double to 4
Check arr[4] = 16 → ≤ 72, double to 8
Check arr[8] = 72 → = 72, FOUND!
✓ 5 gallop jumps → O(log n)
PHASE 2 — BINARY SEARCH 🔍
38
56
72
91
If gallop overshoots, binary search the range
Range = [prevBound, min(bound, n-1)]
Check mid, discard half each step
Repeat until found or range empty
O(log n) comparisons in this phase
✓ Total: O(log n) — same as binary search

// INTERACTIVE VISUALIZER

Watch it
gallop & search.

Pick a target and press play. Watch the galloping phase jump with exponentially increasing steps, then the binary search phase narrow down the exact index.

📖

Imagine finding your friend in a line!

Your friend is somewhere in a very long line of people sorted by height. You don't know how long the line is! Instead of checking person by person, you take bigger and bigger jumps — 1 step, 2 steps, 4 steps, 8 steps, 16 steps... until you jump PAST your friend. Then you go back one jump and binary searchthe small range. That's exponential search!

FIND →
▶️

Press PLAY to start the search!

// READY
0
2
1
5
2
8
3
12
4
16
5
23
6
38
7
56
8
72
9
91
10
108
11
145
12
200
13
256
14
333
CHECKING (mid)
GALLOPED
IN RANGE
DISCARDED
FOUND ✅
Comparisons made
...

// ALGORITHM · STEP BY STEP

The algorithm
in detail.

// FLOWCHART · ALGORITHM VISUALIZATION

// FLOWCHART · Exponential Search
Search for target = 72 in a sorted array of 15 elements
array = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91, 108, 145, 200, 256, 333] · target = 72
YesNoYesNoNoYesYesNoYesNoStartCheck arr[0]bound ← 1bound < n ANDarr[bound] ≤ target ?bound ← bound × 2lo ← bound/2hi ← min(bound, n-1)lo ≤ hi ?mid ← lo +(hi - lo) / 2arr[mid]= target ?arr[mid]< target ?hi ← mid - 1return 0return -1return midlo ← mid + 1

Press PLAY to trace the algorithm through the flowchart.

0 / 27

// PSEUDOCODE · EXECUTION FLOW

// PSEUDOCODE · Exponential Search
Gallop with doubling bounds, then binary search the found range
array = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91, ...] · target = 72
1function exponentialSearch(arr, target):
2if arr[0] = target: return 0
3bound ← 1
4while bound < n AND arr[bound] ≤ target:
5bound ← bound × 2
6lo ← bound / 2
7hi ← min(bound, n - 1)
8while lo ≤ hi:
9mid ← lo + (hi - lo) / 2
10if arr[mid] = target: return mid
11if arr[mid] < target: lo ← mid + 1
12else: hi ← mid - 1
13return -1 // not found

Press PLAY to step through the algorithm line by line.

0 / 27

// EXPONENTIAL VS BINARY

Exponential vs
binary search.

Both are O(log n), but exponential search shines when you don't know the array size. Drag the slider to compare comparison counts.

// EXPONENTIAL_VS_BINARY · ARRAY SIZE = 1,024
16N = 1,0241M
EXPONENTIAL SEARCHO(log n)
checks

Gallop (log n) + binary (log n) = 2·log n

BINARY SEARCHO(log n)
checks

Needs known size. Halve the search space.

For n=1,024, both are O(log n), but exponential search takes roughly 2× more comparisons than binary search. The real advantage: exponential search works on unbounded arrayswhere you don't know n!

When to use Exponential Search

  • Array is sorted but size is unknown (unbounded)
  • Searching infinite or streamed data
  • Target is likely near the beginning
  • Working with linked structures (no random access to end)
  • You need O(log n) but can't precompute array length

When to use Binary Search

  • Array is sorted and size is known
  • You need maximum efficiency (fewer comparisons)
  • Random access is available (arrays, not linked lists)
  • Target could be anywhere in the array
  • You search the same array repeatedly

// COMPLEXITY COMPARISON

AlgorithmTime (Best)Time (Worst)SpaceNeeds Size?
ExponentialO(1)O(log n)O(1)No ✨
BinaryO(1)O(log n)O(1)Yes

// PRACTICE & ASSESS

Test your understanding

Now that you've learned the concept, put it into practice. Solve coding problems and take quizzes to reinforce what you've learned.

💻

Coding Problems

The Galloping Search: Find an Element in a Sorted ArrayL3The Unbounded Array: Search Without Knowing the SizeL4The Doubling Explorer: Find Target in an Infinite Sorted ArrayL5The First Occurrence: Find Leftmost Index with Exponential SearchL4The Range Finder: Locate the Search Range EfficientlyL5The Sorted Matrix: Search in a Row-Column Sorted MatrixL6The Peak in Unbounded: Find a Peak Using Exponential StrategyL6The Insert Position: Find Where to Insert in a Sorted ArrayL4

// TUTORIAL QUIZZES · LEVELS 1–9

Test your mastery

Nine progressive quizzes from Level 1 to Level 9. Each has 10 questions with a 10-minute timer. XP scales with level — L1 gives 10 XP, L9 gives 90 XP. Click a quiz to expand and begin.

// REFERENCES

Sources & further reading

  1. [1]
    Introduction to Algorithms (CLRS)T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein — searching in sorted arrays
  2. [2]
    The Art of Computer Programming, Vol. 3Donald Knuth — Section 6.2.1: searching an ordered table
  3. [3]
    AlgorithmsRobert Sedgewick & Kevin Wayne — exponential and binary search applications
  4. [4]
    Programming PearlsJon Bentley — Column 2: algorithm correctness and search strategies
  5. [5]
    Exponential Search (Galloping Search)Bentley & Yao — "An almost optimal algorithm for unbounded searching" (1976)

// READY?

Master algorithms
with CodeTikki.

Practice 1,000+ coding problems, follow career roadmaps, and get hired.