Exponential Search

Find a target in a sorted list using exponential search with any valid index.

searching sorted-array algorithms

Write a function `exponential_search(arr, target)` that takes a **sorted** list `arr` and a `target` value, and returns **the index** of `target` in `arr`. If `target` is not present, return `-1`.

Exponential search works in two phases: first, find a range `[low, high]` where the target could be by doubling an index from 1 until the value at that index exceeds `target` or the index goes beyond the list. Then, perform a **binary search** within that range to locate an exact index.

You may assume that `arr` is sorted in ascending order. The list may contain duplicates; in that case, you may return **any** index where `target` appears. The exact index among duplicates is not fixed, but it must be a valid index where `target` is present.

Do not use Python's built-in `bisect` module or the `index()` method. Implement the algorithm manually.

Constraints

`0 <= len(arr) <= 10^5`
`arr` is sorted in non-decreasing order.
Elements can be any comparable type (e.g., integers, floats, strings).
Your solution should run in `O(log i)` time where `i` is the position of the target (or where it would be inserted), and `O(1)` extra space.

Example

>>> exponential_search([1, 2, 3, 4, 5], 3)
2
>>> exponential_search([1, 2, 3, 4, 5], 5)
4
>>> exponential_search([1, 2, 3, 4, 5], 0)
-1
>>> exponential_search([], 1)
-1
>>> exponential_search([1, 1, 2, 2, 3], 2)
2  # any valid index, e.g., 2 or 3

10 points ~15 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Start with index 1 and double it until arr[i] >= target or i >= len(arr). Use that as the high bound.

The low bound for the binary search is i//2, and the high bound is min(i, len(arr)-1).

Binary search within that range works exactly like the classic algorithm.

Handle the edge case of an empty list first, and verify the first element in your search.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.