AlgoThrive
← All searching algorithms

Exponential Search

CheckingRuled outFound

array

target = 18
2
4
6
9
12
15
18
20
0
1
2
3
4
5
6
7

pseudocode

exponentialSearch(a, target)
  if a[0] == target return 0
  i = 1
  while i < n and a[i] <= target
    i = i * 2
  return binarySearch(a, target, i/2, min(i, n-1))

Frame 1 / 8

Check index 0 != 18. Start exponential bounds

bound = 1

4

Pick a value that is in the array — or one that isn't, to watch the search fail.

3–16 integers between 1 and 20 — the array is sorted for you, because binary search needs ordered data.