Exponential search in Python
Probe indices 1, 2, 4, and so on until the key is bracketed, then binary search; O(log i) for a key at position i.
- File
exponential_search.py, 36 lines- Level
- I0 not checked yet
- Toolchain
- Python 3.14, pytest 9
- Test framework
- pytest
- Run the tests
python3 -m pytest
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/exponential-search/. The authors are listed in prov/V34DA8.jsonl.
from collections.abc import Sequence
from typing import Protocol, TypeVar
class Ordered(Protocol):
def __lt__(self, other: "Ordered", /) -> bool: ...
T = TypeVar("T", bound=Ordered)
def exponential_search(a: Sequence[T], x: T) -> int:
"""Return the smallest index i with a[i] == x, or -1 when x is not in a.
The list a must be sorted in non-decreasing order. The search tests
a[0], a[1], a[3], a[7], ... until one is not less than x, then runs a
binary search on the last gap. For a key whose lower bound is l >= 1 it
makes at most 2 * floor(lg l) + 3 comparisons.
"""
n = len(a)
b = 1 # @line L1
while b <= n and a[b - 1] < x: # @line L2
b *= 2 # @line L3
lo, hi = b // 2, min(b - 1, n) # @line L4
while lo < hi: # @line L5
mid = lo + (hi - lo) // 2 # @line L6
if a[mid] < x: # @line L7
lo = mid + 1
else: # @line L8
hi = mid
if lo < n and a[lo] == x: # @line L9
return lo
return -1 # @line L10
test_exponential_search.py 94 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/exponential-search/. The authors are listed in prov/V34DA8.jsonl.
import bisect
import random
from exponential_search import exponential_search
A = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91, 99, 104, 120]
class Key:
count = 0
def __init__(self, v: int) -> None:
self.v = v
def __lt__(self, other: "Key") -> bool:
Key.count += 1
return self.v < other.v
def __eq__(self, other: object) -> bool:
Key.count += 1
return isinstance(other, Key) and self.v == other.v
def test_example() -> None:
assert exponential_search(A, 23) == 5
assert exponential_search(A, 72) == 8
assert exponential_search(A, 2) == 0
assert exponential_search(A, 120) == 12
assert exponential_search(A, 1) == -1
assert exponential_search(A, 121) == -1
assert exponential_search(A, 13) == -1
def test_edges() -> None:
assert exponential_search([], 1) == -1
assert exponential_search([4], 4) == 0
assert exponential_search([4], 5) == -1
assert exponential_search([4], 3) == -1
assert exponential_search([7, 7, 7, 7, 7, 7, 7, 7, 7], 7) == 0
def test_first_occurrence_at_powers_of_two() -> None:
# The first copy sits exactly at lo = b / 2 or at hi = b - 1.
for n in range(1, 40):
for start in range(n):
a = [0] * start + [1] * (n - start)
assert exponential_search(a, 1) == start
assert exponential_search(a, 0) == (0 if start > 0 else -1)
def test_every_position_and_gap() -> None:
for n in range(0, 70):
a = list(range(0, 2 * n, 2))
for i in range(n):
assert exponential_search(a, 2 * i) == i
for g in range(-1, 2 * n + 1, 2):
assert exponential_search(a, g) == -1
def test_comparison_bound() -> None:
for n in [1, 2, 3, 13, 64, 100, 1000]:
a = [Key(2 * i) for i in range(n)]
for v in range(-1, 2 * n + 1):
lb = (v + 1) // 2
Key.count = 0
exponential_search(a, Key(v))
bound = 2 if lb == 0 else 2 * (lb.bit_length() - 1) + 3
assert Key.count <= bound
def test_counts_far_from_end() -> None:
a = [Key(i) for i in range(10**5)]
for i, want in [(0, 2), (1, 3), (2, 5), (7, 7), (8, 9), (100, 15), (1000, 21)]:
Key.count = 0
assert exponential_search(a, Key(i)) == i
assert Key.count == want
def test_random_against_bisect() -> None:
rng = random.Random(4417)
for _ in range(3000):
a = sorted(rng.randint(-15, 15) for _ in range(rng.randint(0, 50)))
x = rng.randint(-17, 17)
i = bisect.bisect_left(a, x)
want = i if i < len(a) and a[i] == x else -1
assert exponential_search(a, x) == want
def test_strings() -> None:
assert exponential_search(["ant", "bee", "cat", "dog", "eel"], "ant") == 0
assert exponential_search(["ant", "bee", "cat", "dog", "eel"], "fox") == -1
What the next level needs
- the tests did not run in this build