Exponential search

Prerequisites

• Binary search, which is the second phase.
• Powers of two: 1, 2, 4, 8, 16, …
• Logarithms: $\log_2 i$ doublings reach $i$.

The analogy

How it works

Data requirement: the array must be sorted. Its length may be unknown or unbounded.

Start with one search by hand

Look for 14 in [2, 4, 6, 8, 10, 12, 14, 16, 18, 20]. a[0] = 2 is not it, so start doubling at i = 1. Guess first, then open "Check".

Finish the picture

Try two more targets in the same array.

• Search for 4. Predict: how many doubling steps?
  Check

  None. At i = 1, a[1] = 4 is not < 4, so doubling stops at once and binary search checks the tiny range 0..1.

• Search for 21, bigger than everything. Predict: where does doubling stop?
  Check

  At i = 16, past the end, so hi is clipped to the last index, 9. Binary search on 8..9 then fails: −1.

The rule in plain words

Check the first element. Then check indices 1, 2, 4, 8, … while the value is smaller than the target and you're inside the array.

When you stop at index $i$, run binary search on indices $i/2$ to $\min(i, n-1)$.

The code

Read this code after you have done one search by hand. It will make more sense.

int exponential_search(const int a[], int n, int x) {
    if (n == 0) return -1;
    if (a[0] == x) return 0;
    int i = 1;
    while (i < n && a[i] < x) i *= 2;         /* double until we pass x */
    int lo = i / 2, hi = i < n ? i : n - 1;    /* x is in a[lo..hi] if anywhere */
    while (lo <= hi) {                         /* plain binary search */
        int mid = lo + (hi - lo) / 2;
        if (a[mid] == x) return mid;
        if (a[mid] < x) lo = mid + 1; else hi = mid - 1;
    }
    return -1;
}

flowchart TD
  A{"a[0] == x ?"} -->|yes| B["Return 0"]
  A -->|no| C["i = 1"]
  C --> D{"i < n and a[i] < x ?"}
  D -->|yes| E["i = i * 2"]
  E --> D
  D -->|no| F["Binary search in a[i/2 .. min(i, n-1)]"]
          

How fast is it?

For a target at index $i$, doubling takes about $\log_2 i$ steps and the final range has about $i/2$ elements, so binary search adds another $\log_2 i$:

Common mistakes

• Starting the doubling at i = 0: 0 × 2 stays 0 forever.
• Forgetting to clip hi to n - 1 after the last doubling.
• Searching [0, i] instead of [i/2, i]: still correct, but it throws away what doubling learned.

Try it yourself

Did you know?

Key points to remember

If you remember one thing from each line, remember the because.

• Doubling brackets the target because it stops at the first $i$ where $a[i] \ge x$, so $x$ lies in $[i/2, i]$.
• The cost is $O(\log i)$ because both phases depend only on the target's position $i$, not on $n$.
• It works on unbounded lists because it never needs to know $n$ in advance.
• It needs sorted data because both the doubling test and the binary search rely on order.
• Extra space is $O(1)$ because it only keeps a few indices.

Self-check questions

Answer these in order, out loud. They follow the page, so your answers become the script of your video.

1. How is exponential search like searching a scroll with no visible end?
   Sample answer

   You jump 1, 2, 4, 8 pages ahead until you overshoot, then search back carefully in the last jump. That's doubling, then binary search.

2. Walk through a search for 14 in [2, 4, …, 20].
   Sample answer

   Indices 1, 2 and 4 hold values below 14; index 8 holds 18, so stop. Binary search on 4..8 checks index 6 first and finds 14.

3. Why does the code start doubling at i = 1 and check a[0] separately?

   A good answer says what doubling 0 gives.

   Sample answer

   Doubling 0 gives 0 forever, so the loop would never move. Starting at 1 lets it double, and index 0 is handled by its own check.

4. So what is exponential search, in one sentence?
   Sample answer

   It doubles an index until it passes the target to find a range, then binary searches inside that range.

5. Why is its cost $O(\log i)$ and not $O(\log n)$?

   A good answer looks at both phases.

   Sample answer

   Doubling stops after about $\log_2 i$ steps, and the bracket it finds has about $i/2$ elements, so binary search also takes about $\log_2 i$. Neither phase looks beyond the target's neighbourhood.

6. What are its best, average and worst cases?
   Sample answer

   Best $O(1)$ when the target is at index 0, typically $O(\log i)$, worst $O(\log n)$ when the target is near the end. Extra space $O(1)$.

7. When is it better than plain binary search?
   Sample answer

   When targets are usually near the front of a big array, or when the array's length is unknown or unbounded, so binary search can't pick a middle.

8. If you had to teach this to a friend in 2 minutes, what would you leave out, and why?
   Sample answer

   I'd leave out the clipping detail and the Timsort connection. I'd keep the scroll analogy, the 1-2-4-8 doubling on the example, and "double to bracket, binary search inside, $O(\log i)$".

External resources

• GeeksforGeeks: Exponential search: an article with code and its use on unbounded arrays.
• Wikipedia: Exponential search: history and the $O(\log i)$ analysis.

Videos

• YouTube search: exponential search algorithm: pick a short walkthrough.